[C++] 백준/Gold/20040. 사이클 게임

문제: 사이클 게임 (백준 20040번)

지문을 딱 보자마자 눈살이 찌푸려진다. 처음 이 문제의 지문을 읽었을 때 문제의 의도를 도출하는 데 꽤 시간이 걸렸다. 글자도 많고, 마치 비문학을 읽는 것처럼 의도하는 바가 무엇인지 이해하기 쉽지 않다.

문제 의도와 핵심

이 문제에서 요구하는 결론은 n개의 정점(노드)의 사이클 생성 여부를 알아내라는 것이다. 지문이 복잡하게 설명되었지만, 실제로는 간단한 Union-Find 알고리즘을 활용하여 사이클을 판별하는 문제다.

같은 알고리즘을 사용하는 골드 5 난이도의 문제도 있는 걸 보면, 지문 이해 난이도가 추가되어 골드 4로 책정된가 아닌가 싶다.

문제 요구 사항

• n개의 정점과 m개의 간선이 주어진다.
• 간선이 입력될 때마다 사이클이 발생하는지 확인한다.
• 사이클이 발생하면 해당 입력이 몇 번째인지 출력한다.
• m개의 입력이 모두 주어져도 사이클이 발생하지 않으면 0을 출력한다.

접근 방법: Union-Find 알고리즘

MST나 위상 정렬과 같은 문제에서 자주 쓰이는 Union-Find를 사용하여 사이클을 판별한다. Union-Find는 각 노드끼리 집합을 구성하며, 두 점이 이미 같은 집합에 속해 있다면 사이클이 형성된 것이다.

핵심 아이디어

1. Find 연산: 경로 압축(Path Compression)을 사용해 루트를 효율적으로 찾는다.
2. Union 연산: 랭크(Rank) 기반으로 집합을 병합하여 트리의 높이를 최소화한다.

코드 구현

#include <bits/stdc++.h>
using namespace std;

// Union-Find 자료구조를 위한 parent와 depth 배열
vector<int> parent, depth;

// Find 연산 (경로 압축 적용)
int Find(int x) {
    if (parent[x] != x) {
        parent[x] = Find(parent[x]);
    }
    return parent[x];
}

// Union 연산
bool Union(int x, int y) {
    int rootX = Find(x);
    int rootY = Find(y);
    if (rootX == rootY) return false; // 이미 같은 집합에 속해 있음 (사이클 발생)
    if (depth[rootX] > depth[rootY]) {
        parent[rootY] = rootX;
    }
    else if (depth[rootX] < depth[rootY]) {
        parent[rootX] = rootY;
    }
    else {
        parent[rootY] = rootX;
        depth[rootX]++;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    parent.resize(n);
    depth.resize(n, 0);

    // 초기화
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        // 사이클이 발생하면 i번째 차례 출력
        if (!Union(a, b)) {
            cout << i << '\n';
            return 0;
        }
    }

    // 모든 차례를 처리한 후에도 사이클이 없으면 0 출력
    cout << 0 << '\n';
    return 0;
}

 

1. 초기화
   • parent 배열: 각 노드는 초기에는 자기 자신을 부모로 설정한다.
   • depth 배열: 모든 노드의 깊이를 0으로 초기화한다.
2. Find 연산
   • 재귀적으로 부모 노드를 찾아가며 경로를 압축하여 효율성을 높인다.
3. Union 연산
   • 두 노드의 루트를 비교하여 랭크를 기반으로 병합한다.
   • 두 노드가 이미 같은 집합에 속해 있다면 사이클이 형성된 것으로 판단한다.
4. 입력 처리
   • 간선 정보를 입력받으며 Union 연산을 수행한다.
   • 사이클이 발생하면 해당 차례의 번호를 출력하고 종료한다.
   • 모든 간선을 처리한 후에도 사이클이 없으면 0을 출력한다.