[작성중]ABC 399 D, E (논리딸리는 스왑문제, 많조분애드혹 플래2)

저번주에 앳코더 털리고 논리가 딸려서 슬프다는 소리를 했는데 이번에도 비슷하게 논리로 털린 것 같다

문제를 코드로 옮기기 전 확실한 설계가 필요함을 되새기면서 문제를 다시 풀어 보자

 

예전에도 잘하진 못했는데 AI로 사기치는 비양심유저들이 등장하면서 문제가 특히 지랄맞아진것같다고

생각하면 안된다. 더욱 정진하자

내 목표는 앳코더 민트랑 모비스 대회 본선진출

 

D : 1~N까지 숫자가 2번씩 등장하는 수열에서, 스왑 X번을 해서 같은 원소끼리 인접시키는 문제

맞왜틀??

https://atcoder.jp/contests/abc399/tasks/abc399_d

D - Switch Seats

문제 이해

1~N까지 숫자가 각각 2번씩 등장하는 길이 2N짜리 수열이 있는데

원소 2개를 골라서 원하는 만큼 스왑합니다. 모든 원소들이 자기 짝꿍이랑 인접하게 되면 끝임

이렇게 하기 위한 최소의 스왑 횟수를 구하시오

 

>> 그리디하게 생각했다

모든 원소들이 자기 짝꿍이랑 인접하기 위해선 길이 2N짜리 수열의 원소들을 2개씩 끊어서 보면 된다.

첫번째 원소부터 마지막 원소까지 쭉 훑으면서 2개씩 끊어서 보고

짝꿍이 없는 녀석은 set에 넣어놨다가 유니온파인드로 연결하면서... 나름대로 업데이트??를 했다

//틀린 코드
#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
using namespace std;

int parent[200001];
int fp(int n){
    if(parent[n]==n)return n;
    return parent[n]=fp(parent[n]);
}

int main()
{
    fastio;
    int T;cin>>T;//20만
    while (T--)
    {
        int N;cin>>N;//20만
        int ans = 0;
        for (int i = 1; i <= N; i++)parent[i]=i;
        for (int i = 0; i < N; i++)
        {
            int a,b;
            cin>>a>>b;
            int pa = fp(a);
            int pb = fp(b);
            if(pa==pb)continue;
            parent[pa]=pb;
            ans++;
        }
        cout<<ans<<"\n";
    }
    return 0;
}

근데 왜 안됨??

나는 지금까지 업솔빙을 소홀히 했다. 그 이유는 에디토리얼이 정말 안 읽힌다는 것도 한몫한다

GPT의 힘을 빌려서 에디토리얼을 생성해보자

 

 

 

E : 알파벳 바꾸기를 그래프로 바꿔서 사이클 찾고 케이스처리하는끔찍한문제

https://atcoder.jp/contests/abc399/tasks/abc399_e

E - Replace

백준에 똑같은 문제가 있다(플래티넘 2). solved.ac 디스코드를 눈팅하던 중 고인물들이 알려줬다.

https://www.acmicpc.net/problem/27558

문제를 풀면서 많은 조건 분기로 인해 끔찍한 경험을 했다.

아이디어에 도달하는 과정은 그리 어렵지 않다. 어떤 문자를 다른 문자로 바꾸는 것은 끽해봤자 일차원 배열에 그녀석이 어떤 문자로 변했는지 저장해 놓는 일이고, 이것을 outdegree가 최대 1인 그래프처럼 생각할 수 있다는 것 역시 어려운 아이디어가 아님

근데 예외처리가 날 죽여주십시오 수준이다. 플래티넘 문제 많이 풀어보지도 않았고 신나는 날먹을 즐겨왔는데 갑자기 플래 2 애드혹 많조분 문제를 붙잡고 풀게 될지는 몰랐지

 

문제 이해

String 2개가 주어진다. 원본 문자열과 목표 문자열

원본 문자열의 알파벳을 골라서 원하는 알파벳으로 바꿀 수 있는데, 한번 변환해 문자열 내 한개의 char이 바뀌는 게 아니라 문자열에 포함된 동일한 알파벳들이 한번에 다 바뀐다

위 짓거리를 해서 원본 문자열을 목표 문자열로 바꿀 수 없다면 -1을 출력

가능하다면 바꾸기 위한 최소 연산 횟수를 출력한다.

 

아이디어 도출

알파벳을 다른 알파벳으로 바꾸는 것은 그래프상에서 다른 알파벳 한개를 가리키는 것과 같다

그리고 끽해봤자 일차원 그래프다. 그리고 방향 그래프다. 사이클은 있을 수도 있고 없을 수도 있다.

모든 노드들이 하나의 그래프로 엮여 있을 수도 있고 아닐 수도 있다.

그리고 한 알파벳이 다른 문자 두개로 바뀔 순 없으니까 out degree는 최대 1임.

 

구현

E번 문제가 이정도 아이디어로 풀린다고?라고 생각하면서 구현을 신나게 시작함

구현이 살짝 귀찮긴 한데 그래도 5분정도 짜면 대충 굴러가는 코드가 나온다.

 

예외처리 : 한번에 두 노드를 가리키는 노드

한 알파벳이 다른 문자 두개로 바뀔 순 없으니까 out degree는 최대 1이다.

그렇기 때문에 처음에 문자열 S와 T를 받고, S와 T를 연결하는 그래프(1차원 배열)을 만드는 부분에서 이걸 체크하고 바로 -1을 리턴할 수 있다.

 

예외처리 : 사이클

예제를 살펴보면 사이클에 의한 예외가 발생함을 알 수 있다.

A에서 B로, B에서 A로 가는 간선이 존재할 경우 크기가 2인 사이클이 발생했다. 이 경우

원본 문자열 AB를 목표 문자열 BA로 바꾸기 위해선 다른 노드를 중간에 한번 거쳐야 한다. 예를 들어 C라는 노드를 거친다고 하면

AB -> CB -> CA -> BA 이런식으로, 사이클이 아니라면 2번이면 될 변환을 3번 걸려서 해야 함.

그래서 사이클의 개수를 체크하고 마지막 답 출력할 때 사이클의 개수를 더해주자~ 라고 생각했음.

 

예외처리 : self-loop의 경우

근데 위의 상황에서 C가 self loop를 가진다면 중간 노드로 C를 거쳐갈 수 없다.

원본 문자열 ABC 목표 문자열 BAC

이 경우 C는 변환 횟수를 소모하지 않지만, 그냥 중간 노드로 쓸 수 없는 애가 됨. 그래서 self loop를 갖는 애들을 따로 체크해주기로 했다. 이때부터 똥냄새가 스멀스멀 나기 시작. self loop를 갖는 애들은 사이클에 카운트해서는 안된다는 점도 똥냄새를 더하는 부분이다

이 예외처리를 잘못 처리하면 S==T인 경우에도 -1을 출력하는 똥내나는 실수를 하게 될 수 있으니

맨 앞에 S==T이면 0을 리턴하는 코드도 넣어 줘야 함.

 

예외처리 : 모든 노드(알파벳)이 사용 중일 경우

크기 2 이상인 사이클이 존재하는데, 중간 노드로 거쳐갈 수 있는 노드가 단 하나도 없다면 -1을 출력해야 한다.

이미 내 코드는 스파게티 코드인데 어떡함?? 개말린다

코드를 갈아치우고 다시 짜기 좋은 타이밍이다.

아무튼 이 예외를 처리하기 위해선 자신에게서 나가는 간선을 갖는 모든 노드를 체크해 놔야 함. 그 노드들은 중간 노드로 거쳐갈 수 없다.

 

예외처리 : 모든 노드가 사용 중이지만 사이클에 포함되지 않은 어느 원소가 사이클의 원소를 가리키고 있을 경우

 

예외처리 : 모든 노드가 사용 중이지만 사이클에 포함되지 않은 어느 원소가 사이클의 원소를 가리키고 있고 그걸 가리키는 노드가 또 있을 경우

 

예외처리 : 모든 노드가 사용 중이지만 사이클에 포함되지 않은 어느 원소가 사이클의 원소를 가리키고 있고 또다른 사이클이 존재할 경우

 

예외처리 : 모든 노드가 사용 중이지만 사이클에 포함되지 않은 어느 원소가 사이클의 원소를 가리키고 있고 또다른 사이클에서 사이클에 포함되지 않은 어느 원소가 그 사이클의 원소를 가리키고 있을 경우