boj 20040 사이클게임(Union-Find) Java

문제

사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 번호가 부여된 평면 상의 점 n 개가 주어지며, 이 중 어느 세 점도 일직선 위에 놓이지 않는다. 매 차례 마다 플레이어는 두 점을 선택해서 이를 연결하는 선분을 긋는데, 이전에 그린 선분을 다시 그을 수는 없지만 이미 그린 다른 선분과 교차하는 것은 가능하다. 게임을 진행하다가 처음으로 사이클을 완성하는 순간 게임이 종료된다. 사이클 C는 플레이어가 그린 선분들의 부분집합으로, 다음 조건을 만족한다.

C에 속한 임의의 선분의 한 끝점에서 출발하여 모든 선분을 한 번씩만 지나서 출발점으로 되돌아올 수 있다.

문제는 선분을 여러 개 그리다 보면 사이클이 완성 되었는지의 여부를 판단하기 어려워 이미 사이클이 완성되었음에도 불구하고 게임을 계속 진행하게 될 수 있다는 것이다. 이 문제를 해결하기 위해서 게임의 진행 상황이 주어지면 몇 번째 차례에서 사이클이 완성되었는지, 혹은 아직 게임이 진행 중인지를 판단하는 프로그램을 작성하려 한다.

입력으로 점의 개수 n과 m 번째 차례까지의 게임 진행 상황이 주어지면 사이클이 완성 되었는지를 판단하고, 완성되었다면 몇 번째 차례에서 처음으로 사이클이 완성된 것인지를 출력하는 프로그램을 작성하시오.

입력

입력은 표준입력을 사용한다. 입력의 첫 번째 줄에는 점의 개수를 나타내는 정수 3 ≤ n ≤ 500,000 과 진행된 차례의 수를 나타내는 정수 3 ≤ m ≤ 1,000,000 이 주어진다. 게임에서 사용하는 n개의 점에는 0 부터 n − 1 까지 고유한 번호가 부여되어 있으며, 이 중 어느 세 점도 일직선 위에 놓이지 않는다. 이어지는 m 개의 입력 줄에는 각각 i번째 차례에 해당 플레이어가 선택한 두 점의 번호가 주어진다 (1 ≤ i ≤ m).

출력

출력은 표준출력을 사용한다. 입력으로 주어진 케이스에 대해, m 번째 차례까지 게임을 진행한 상황에서 이미 게임이 종료되었다면 사이클이 처음으로 만들어진 차례의 번호를 양의 정수로 출력하고, m 번의 차례를 모두 처리한 이후에도 종료되지 않았다면 0을 출력한다.

예제 입력 1

6 5
0 1
1 2
2 3
5 4
0 4

예제 출력 1

0

예제 입력 2

6 5
0 1
1 2
1 3
0 3
4 5

예제 출력 2

4

최근 최소스패닝트리(MST) 공부하면서 Union-Find를 알고있어서 적용하면 풀렸다..ㅎ

코드 작동!

각각의 점이 자신을 부모로 하는 집합을 초기화합니다.
각각의 입력에 대해서, 두 점이 같은 집합에 속하는지 확인합니다. 만약 두 점이 같은 집합에 속한다면, 그것은 사이클을 형성한다는 것을 의미하므로, 그 시점의 게임 횟수를 출력하고 종료합니다.
만약 두 점이 같은 집합에 속하지 않는다면, 두 집합을 합치고 다음 입력을 확인합니다.
모든 입력을 확인했는데도 사이클이 형성되지 않았다면, 0을 출력합니다. 이는 주어진 입력으로는 사이클이 형성되지 않는다는 것을 의미합니다.

import java.io.*;
import java.util.*;

public class Main {
    // 부모 노드를 가리키는 배열 선언
    static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // n은 점의 개수, m은 게임을 진행한 횟수
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        parent = new int[n];
        // 초기화, 모든 노드를 각각의 부모로 설정 (자기 자신이 부모임)
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }

        int cycle = 0;
        for (int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine());
            // 게임에서 이어진 두 점
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            // 두 점이 같은 부모를 가지고 있다면 사이클이 생긴 것
            if (find(a) == find(b)) {
                cycle = i;
                break;
            } else {
                // 사이클이 아니면 두 점을 이어준다 (같은 부모를 가지게 한다)
                union(a, b);
            }
        }
        // 사이클이 생긴 경우 사이클이 생긴 게임의 횟수 출력, 생기지 않은 경우 0 출력
        System.out.println(cycle);
    }

    // 경로 압축(Path Compression)을 사용한 find 함수
    static int find(int x) {
        // x의 부모가 x와 같다면 (즉, 자기 자신이 부모라면) x 반환
        if (x == parent[x]) {
            return x;
        }
        // 아니라면 부모를 찾아가는 과정에서 경로 압축 실행
        return parent[x] = find(parent[x]);
    }

    // a 집합과 b 집합을 합치는 함수
    static void union(int a, int b) {
        a = find(a);
        b = find(b);
        // a와 b의 부모가 다르다면 (즉, 같은 집합이 아니라면) b의 부모를 a로 설정
        if (a != b) {
            parent[b] = a;
        }
    }
}