[BOJ/백준] 20040 사이클 게임 (G4)

문제

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

풀이

문제를 정리해보면 0부터 n-1 까지의 고유한 번호가 부여된 평면상의 점 n개가 주어지며, 이 중 어느 세점도 일직선 위에 놓이지 않는다.

매 차례마다 이를 잇는 선분을 그린다. → 이전에 그은 선분을 다시 글을 수 없으며, 이미 그린 선분과 교차는 가능하다.

처음으로 사이클(플레이어들이 그린 선분들의 부분집합)이 완성되는 순간 게임이 종료된다.

게임의 진행 상황이 주어지면 몇 번째 차례에서 사이클이 완성 되었는지를 판단하고, 혹은 게임이 진행 중인지를 판단하는 프로그램을 작성해야 한다.

 

연결을 할 때마다 카운트를 하며 사이클이 생기면 종료를 해야하는데, 사이클을 판단하는 방법으로 Union-find 자료구조를 사용하면 된다.

Union-find를 사용하면 각 점을 연결시켜 사이클이 발생하는 구간에서 값을 반환해주면 된다.

find 함수는 부모를 반환한다

static int find(int x) {
    if (x == parent[x])
        return x;
    // 재귀 탐색을 하여 parent[x]를 갱신하며 최상위 부모 노드에 빠르게 접근한다.
    return parent[x] = find(parent[x]);
}

union 함수로 x, y를 연결한다.

static void union(int x, int y) {
    x = find(x);
    y = find(y);

    if (x < y) {
        parent[y] = x;
    } else
        parent[x] = y;
}

작은 수를 가지는 지점이 무조건 부모가 된다.

 

즉, x, y의 두 정점이 주어지면 부모(최상위 부모)가 일치하는지 확인한다. 만약 if(find(x) == find(y))로 부모가 일치한다면, 사이클이 생성된 것이므로 구간을 출력하고 반환하여 종료한다. x, y가 일치하지 않으면 서로 다른 부모를 가지고 있는 것이므로 union(x, y)를 하여 두 정점을 연결한다.

Code

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

public class Main {

    static int n, m;
    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;

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

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

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            if (find(x) == find(y)) {  // 부모가 같아지므로, 사이클이 형성됨
                bw.write(i + 1 + "");
                bw.flush();
                bw.close();  // 출력하고 종료
                return;
            } else {
                union(x, y);
            }
        }
        bw.write("0");
        bw.flush();
        bw.close();
    }

    static int find(int x) {
        if (x == parent[x])
            return x;
        // 재귀 탐색을 하여 parent[x]를 갱신하며 최상위 부모 노드에 빠르게 접근한다.
        return parent[x] = find(parent[x]);
    }

    static void union(int x, int y) {
        x = find(x);
        y = find(y);

        if (x < y) {
            parent[y] = x;
        } else
            parent[x] = y;
    }
}