[백준] 20040번 - 사이클 게임 (Gold 4)

문제 링크

[백준] 20040번 - 사이클 게임 (Gold 4)

문제 설명

점의 개수 n, 선분의 개수 m, m개의 선분이 순서대로 입력으로 주어진다.
첫번째 선분부터 시작해서 몇개의 연속한 선분을 사용해야 최초의 사이클이 형성되는지를 출력한다.
사이클이 m개의 선분을 모두 사용하여도 형성되지 않는다면 0을 출력한다.

정답 코드 및 설명

유니온 파인드 알고리즘을 통해 해결할 수 있다.
처음에는 각 점이 모두 다른 집합에 있다가, 선분으로 이어지면 두 집합을 합치는 과정을 반복한다.
이미 같은 집합에 있는 두 점이 입력으로 들어왔다면 사이클이 형성된 것이다.

유니온 파인드 알고리즘을 이 문제에서는 다음과 같이 구현하였다.
집합을 트리 구조로 생각하는 것은 동일하다.

1. 배열 parents[]을 만든다.
2. i번째 원소가 루트 노드이면 parents[i]에 -(집합의 크기)를 넣는다.
3. i번째 원소가 루트 노드가 아니면 parents[i]에 부모 노드를 넣는다.
4. 두 집합을 합칠 때는 집합의 크기가 큰 쪽으로 합친다.

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

public class BOJ20040 {
    int n, m;
    int[] parent;

    void solution() 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());
        parent = new int[n];
        Arrays.fill(parent, -1);
        int ans = 0;
        for (int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            if (isInSameSet(v1, v2)) {
                ans = i;
                break;
            }
            union(v1, v2);
        }
        System.out.println(ans);
    }

    int findSet(int v) {
        int s = parent[v];
        if (s < 0) return v;
        return findSet(s);
    }

    boolean isInSameSet(int v1, int v2) {
        return findSet(v1) == findSet(v2);
    }

    void union(int v1, int v2) {
        if (isInSameSet(v1, v2)) return;
        int s1 = findSet(v1);
        int s2 = findSet(v2);
        // s1이 더 큰 집합인 경우
        if (-parent[s1] >= -parent[s2]) {
            parent[s1] = parent[s1] + parent[s2];
            parent[s2] = s1;
        } else { // s2가 더 큰 집합인 경우
            parent[s2] = parent[s1] + parent[s2];
            parent[s1] = s2;
        }
    }

    public static void main(String[] args) throws IOException {
        new BOJ20040().solution();
    }
}