[BOJ] 20040번 사이클 게임 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {
    static int N, M, result;
    static int[] parent;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        init();
        process();
        print();
    }

    private static void init() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        parent = new int[N];
        // 부모 테이블 초기화
        initParent();
    }

    private static void initParent() {
        for (int i = 0; i < N; i++) {
            parent[i] = i;
        }
    }

    private static void process() throws IOException {
        // 연산 입력
        StringTokenizer st = null;
        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 (!unionParent(a, b)) {
                result = i;
                break;
            }
        }
    }

    private static boolean unionParent(int a, int b) {
        a = findParent(a);
        b = findParent(b);
        if (a == b) return false;
        parent[b] = a;
        return true;
    }

    private static int findParent(int x) {
        if (parent[x] == x) return x;
        return parent[x] = findParent(parent[x]);
    }

    private static void print() {
        System.out.println(result);
    }
}

📄 해설

• 서로소 집합 알고리즘을 사용해서 그래프의 사이클을 판별하는 문제
• 서로소 집합에서, 두 노드의 루트노드가 같다면 이는 사이클이 발생하는 상태이므로, union 연산 수행 시 두 노드의 루트노드가 같으면 수행이 불가능 한 점을 활용하였음
• union 연산 수행이 불가능하다면 사이클이 발생한 것이므로, result 의 값을 갱신
• 모든 union 연산이 성공적으로 수행되었다면, 사이클이 발생하지 않는 것이므로, result 의 값은 계속해서 0 인 상태