BOJ_20040 : 사이클 게임

👉 문제링크

20040번: 사이클 게임

---

🔸 문제 분석 🔸

• n개의 점들 사이에 m개의 선분을 그을 때, 사이클이 생기는 시점을 확인한다.
• 사이클이 처음 생긴 순서를 출력한다. 사이클이 생기지 않으면 0을 출력한다.

🔸 문제 풀이 🔸

• 분리 집합(Disjoint Set)을 이용해 사이클이 생기는 시점을 파악한다.

🔸 코드 🔸

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

public class Main {

    private static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        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 answer = 0;

        for (int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine());
            if (!union(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()))) {
                answer = i;
                break;
            }
        }

        bw.write(Integer.toString(answer));
        bw.flush();
    }

    private static int find(int a) {
        if (parent[a] == a) return a;
        return parent[a] = find(parent[a]);
    }

    private static boolean union(int a, int b) {
        int ap = find(a);
        int bp = find(b);

        if (ap == bp) return false;
        else if (a == ap && b == bp) parent[ap] = bp;
        else parent[bp] = ap;

        return true;
    }
}

🔸 코드 해석 🔸

• 부모 인덱스를 가리키는 int배열 parent를 선언하고, 각 인덱스 값으로 초기화한다.
• find() 메서드는 저장된 인덱스를 타고 가며 최종 루트 인덱스를 찾고, 해당 인덱스로 자식 인덱스의 값을 변경 후 반환한다.
• union() 메서드는 두 점의 루트 인덱스를 찾는다.
  • 두 루트 인덱스가 같으면, 같은 집합에 연결하게 되므로 사이클이 생긴다. false를 반환한다.
  • 기본은 bp 인덱스의 부모를 ap로 저장한다.
  • 만약 a가 부모 인덱스가 없고, b는 있을 경우에는 ap 인덱스에 bp를 저장한다.
• union() 결과가 false가 나온 순서를 출력한다. 만약 false가 나오지 않으면 0을 출력한다.

---

🔸 end 🔸

•  분리 집합 문제인걸 바로 알아서 어렵지 않게 풀이할 수 있었다. 근데 웃긴건 지금까지 분리 집합(Disjoint Set)을 Union-Find 알고리즘일고 불렀다. 사용되는 메서드를 기억하기 좋았지만 제대로 기억하도록 하자.