[Union and Find] 백준 20040 사이클 게임

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

20040번: 사이클 게임

 

N 명의 선수가 선분을 번갈아가면서 그리는 게임을 M 차례까지 진행했을 때,

 

중간에 사이클이 생긴다면 사이클이 생겼던 회차를,

 

M 번 진행하는 동안 사이클이 발생하지 않았다면 0 을 출력하면 된다.

 

예제를 통해 생각해보자.

 

0 과 1 을 선택하여 0-1 선분을 긋는다는 것은 0 과 1 은 같은 집합으로 Clustering 된다는 것이다.

m 번의 회차마다 주어지는 두 포인트를 같은 집합으로 Clustering 하는 작업을 거칠 때, 사이클을 이루는 경우가 없으므로 답은 0 이다.

 

마찬가지로 m 번의 회차마다 주어지는 두 점을 하나의 집합으로 clustering 을 진행한다.

그러다 보면 m = 4 일 때, 이미 같은 집합에 놓인 두 포인트를 같은 집합으로 clustering 하는 상황이 발생하며 이러한 경우에는 사이클이 발생한 것이라고 할 수 있다. 왜냐면 0 -> 1-> 3-> 0 의 순환 구조가 형성되었기 때문이다.

 

문제 상황은 이해했고, 이를 어떻게 구현할까?

 

같은 집합으로 합치고, 찾고 이런 연산을 반복해야 하는데..

 

그러면 유니온 파인드를 사용할 수 있겠다.

 

시간복잡도를 생각해보면,

 

union 연산은 find 연산에 전적으로 의존하는데

 

find 연산을 구현할 때 경로를 단축시켜 시간복잡도를 줄이는 방법이 보편화되어있다.

 

그렇게 했을 때에 시간 복잡도는 애커만 함수를 이용하여 O(a(N)) 이라고 한다.

 

x 가 2^65536 일 때 a(x) 이 5 가 된다고 하므로 O(a(N)) ~= O(1) 이라고 생각해도 무리는 없겠다.

 

그러므로, 유니온 파인드를 사용해도

 

시간 복잡도에 제한 없이 해결이 가능할 것이라는 것을 예상할 수 있다.

 

전체 코드는 아래와 같다.

 

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

public class Main {
    static int n; // 점의 개수
    static int m; // 현재 진행된 차례의 수
    static int[] parent;

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk;

        stk = new StringTokenizer(br.readLine());
        n = Integer.parseInt(stk.nextToken());
        m = Integer.parseInt(stk.nextToken());

        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }

        int ans = 0;
        for (int i = 1; i <= m; i++) {
            stk = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(stk.nextToken());
            int b = Integer.parseInt(stk.nextToken());
            if(isitsame(a, b)){
                ans = i;
                break;
            } else {
                union(a, b);
            }
        }

        bw.write(ans+"\n");
        bw.flush();
        bw.close();
    }
    private static void union(int a, int b){
        a = find(a);
        b = find(b);
        if(a!=b){
            parent[b] = a;
        }
    }
    private static int find(int a){
        if(parent[a] == a){
            return a;
        } else {
            return parent[a] = find(parent[a]);
        }
    }
    private static boolean isitsame(int a, int b){
        a = find(a);
        b = find(b);
        if(a==b){
            return true;
        } else return false;
    }
}