[백준] 20040 사이클 게임 - 자바

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

20040번: 사이클 게임

문제 풀이

각 노드를 이었을 때 사이클이 생기는지 판단하는 문제로 union-find 알고리즘을 적용하여 쉽게 해결할 수 있다.

 

기본적인 union-find문제는 각 노드마다 부모노드를 저장하여 루트노드까지 순회하며 사이클을 비교한다. 사이클은 같은 루트노드를 가지는 노드끼리 연결했을 때 발새한다.

 

부모노드를 저장하여 루트노드까지 순회하는 과정에서 O(N)의 시간복잡도가 소요된다. 부모노드가 아닌 처음부터 루트노드(최고조상)를 저장하도록 구현하면 더욱 효율적인 시간복잡도를 가진다.

 

따라서 필자는 parent라는 부모 대신 ancestor라는 조상의 의미를 가지는 변수로 대체하였다. (사실 상관없음)

 

각 간선이 주어졌을 때 합칠 수 있는지를 비교하고 같은 루트노드를 가지면 사이클이므로 출력 조건에 맞게 출력해주면 된다.

for (int i = 1; i <= M; i++) {
    st = new StringTokenizer(br.readLine());
    int from = Integer.parseInt(st.nextToken());
    int to = Integer.parseInt(st.nextToken());

    if (!union(from, to)) {
        System.out.println(i);
        return;
    }
}

기본적으로 루트노드가 더 작은 값을 가질 수 있도록 설정했지만 커도 되고, 아예 설정하지 않아도 이 문제에선 전혀 지장이 없다.

static boolean union(int a, int b) {
    int aAncestor = findAncestor(a);
    int bAncestor = findAncestor(b);

    if (aAncestor == bAncestor) // 같으면 순환
        return false;
    // 루트 노드는 작은 값으로 지정
    if (aAncestor > bAncestor)
        ancestor[aAncestor] = bAncestor;
    if (aAncestor < bAncestor)
        ancestor[bAncestor] = aAncestor;
    return true;
}

각 노드는 자신이 속한 그룹의 루트 노드를 가지고 있다. 만약 n==ancestor[n]이라면 이 노드가 루트 노드라는 뜻이다.

static int findAncestor(int n) {
    if (n != ancestor[n]) {  // 루트 노드가 아니라면
        ancestor[n] = findAncestor(ancestor[n]);
    }
    return ancestor[n];
}

여기서 중요한 부분이 ancestor[]에 최고 조상을 가지고 있으니 바로 ancestor[a] == ancesotr[b]를 비교하면 되는 거 아니냐? 라고 생각할 수 있지만 들어오는 간선에 따라서 루트 노드에 대한 업데이트가 필요하다.

위 그림처럼 더 작은 값의 노드가 더 늦게 들어온다면 기존 1을 루트 노드로 갖고 있던 노드들에 대해 업데이트가 필요하다.

물론 2는 나중에 2를 연결하는 간선이 들어오면 그때 find(1)을 호출하고 다시 find(0)을 호출하며 업데이트가 이루어질 것이다.

 

코드

package 백준;

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

public class b20040 {
    static int[] ancestor;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // init
        ancestor = new int[N];
        for (int i = 0; i < N; i++) {
            ancestor[i] = i;
        }

        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());

            if (!union(from, to)) {
                System.out.println(i);
                return;
            }
        }
        System.out.println(0);
    }

    static boolean union(int a, int b) {
        int aAncestor = findAncestor(a);
        int bAncestor = findAncestor(b);

        if (aAncestor == bAncestor) // 같으면 순환
            return false;
        // 루트 노드는 작은 값으로 지정
        if (aAncestor > bAncestor)
            ancestor[aAncestor] = bAncestor;
        if (aAncestor < bAncestor)
            ancestor[bAncestor] = aAncestor;
        return true;
    }

    static int findAncestor(int n) {
        if (n != ancestor[n]) {  // 루트 노드가 아니라면
            ancestor[n] = findAncestor(ancestor[n]);
        }
        return ancestor[n];
    }

}