[백준 코딩테스트] 20040번 사이클게임

내 풀이

처음에는 큐에 넣어서 풀어야하나 따로 Point 클래스를 만들어 각 점을 저장해야하나에 대한 고민이 많았는데 Union-Find 알고리즘을 사용해봐야 겠다는 생각이 들었다.

경로 압축을 통해 각 노드들에 연결된 최상위 노드와 연결시켜 결론적으로 최상위 노드와 입력받은 두 노드가 일치한다면 사이클이 만들어지는 것으로 간주하였다.

경로 압축

Union-Find 알고리즘에서 사용되는 최적화 기법 중 하나로 연산의 효율을 높이기 위한 방법이다.
find(x) 함수는 노드 x가 속한 집합의 대표 노드를 찾는다. 경로 압축은 이 find 과정을 최적화하는 방법으로 찾는 과정에서 만나는 모든 노드를 해당 집합의 루트로 바로 연결시킨다.

5 -> 4 -> 3 -> 2 -> 1과 같은 과정을 거쳐 최종적으로 1을 반환한다고 하자. find(5)를 호출할 때 경로상에 있는 모든 노드를 대표 노드 1에 바로 연결한다. 이렇게되면 5 -> 1, 4 -> 1, 3 -> 1, 2 -> 1로 각 노드가 루트 노드에 바로 연결된다.

위의 20040번 문제도 이와 동일하게 푼다.

내 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Main {
    static int[] arr; 
    static int n, m;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[n+1];

        for(int i=1; i<=n; i++) arr[i] = i; // 배열 초기화. 각 노드들이 자기 자신을 갖도록

        for(int i=1; i<=m; i++){
            st = new StringTokenizer(br.readLine());

            int a = find(Integer.parseInt(st.nextToken()));
            int b = find(Integer.parseInt(st.nextToken()));

            if(a == b){ // 처음으로 사이클이 완성된 경우
                System.out.println(i);
                return ;
            }

            if(a>=b) arr[a] = b;
            else arr[b] = a;
        }

        System.out.println(0); // 사이클이 없으면 0 출력

        
    }

    static int find(int x){ // 사이클을 찾기 위해 특정 노드가 속한 집합의 대표 노드를 찾음
        if(arr[x] == x) return x;
        return arr[x] = find(arr[x]); // 만나는 모든 노드를 해당 집합의 대표 노드와 연결함
    }
}