[ 백준 ] 20040 사이클 게임

Link | 백준 20040번 문제 : 사이클 게임

📌 About

부분 집합을 통해 문제를 해결할 수 있다.

이는 Union & find 알고리즘을 통해 구현할 수 있다.

📌 Solution

M개의 선분을 차례대로 탐색한다.

선분을 탐색할 때 우선 find 함수를 통해 두 선분을 이었을 때 cycle이 생기는지 판단한다.

Cycle이 생기면 해당 순서에서 cycle이 발생한 것이다.

Cycle이 생기지 않는다면 union 함수를 통해 선분을 부분 집합에 추가해준다.

📌 Code

GitHub Repository

private int[] roots;

public void solve() throws IOException {
    StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
    int N = Integer.parseInt(tokenizer.nextToken());
    int M = Integer.parseInt(tokenizer.nextToken());

    roots = IntStream.range(0, N).toArray();
    int m = 1;
    for (; m <= M; m++) {
        tokenizer = new StringTokenizer(reader.readLine());
        int nodeA = Integer.parseInt(tokenizer.nextToken());
        int nodeB = Integer.parseInt(tokenizer.nextToken());
        int rootA = find(nodeA);
        int rootB = find(nodeB);
        if (rootA == rootB) break;
        union(rootA, rootB);
    }
    result.append(m <= M ? m : 0);
}

private int find(int node) {
    if (node == roots[node]) return node;
    else return find(roots[node]);
}

private void union(int rootA, int rootB) {
    if (rootA < rootB) roots[rootB] = rootA;
    else roots[rootA] = rootB;
}