[백준 20040번] [Union-Find] 사이클 게임

전형적인 유니온-파인트(DisjointSet) 문제이다.

왜냐하면, 사이클이 형성된다는 것의 의미는 사실 상 점들의 집합에 속하는 것끼리 연결했다는 것을 의미하기 때문이다.

즉, 해당 집합에 속하는지 속하는지 않는지를 배타적으로 판단해주어야 한다.

이러한 측면에서 Disjoint Set(상호 배타적 집합)을 잡았어야 한다.

 

기본적인 알고리즘은 다음과 같다.

1. Union-Find algorithm을 사용한다.
Init > find > merge 함수를 구현한다.

다만, 이 방법을 사용할 때 Union by rank, Path compression을 활용하여 Time complexity를
O(lg*n)로 낮춘다.

2. 사이클을 형성한다는 것의 의미는 두 점이 이미 같은 집합 안에 들어와있는 경우이다.
즉, Input 2개의 값에 대해서 같은 집합에 속하는지를 먼저 체크하고 같은 집합이면 몇 번째에 해당하는지를 출력해주면 된다.

코드는 다음과 같다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
int visited[500000] = {0};

struct DisjointSet{
    vector<int> parent, rank;
    DisjointSet(int n) : parent(n), rank(n, 1){
        for(int i = 0; i < n; i++){
            parent[i] = i;
        }
    }

    int find(int n){
        if(parent[n] == n) return n;
        else return parent[n] = find(parent[n]);
    }

    void merge(int n, int m){
        n = find(n); m = find(m);

        if(n == m) return;
        // 무조건적으로 rank가 n이 더 크게 끔 설정
        if(rank[n] < rank[m]) swap(n, m);
        parent[m] = n;
        if(rank[n] == rank[m]) rank[n]++;
        return;
    }
};

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N, M;
    cin >> N >> M;
    DisjointSet world(N);

    for(int i = 0; i < M; i++){
        int temp1, temp2;
        cin >> temp1 >> temp2;
        if(world.find(temp1) == world.find(temp2)){
            cout << i + 1 << "\n";
            return 0;
        }
        else{
            world.merge(temp1, temp2);
        }
    }

    cout << 0 << "\n";

    return 0;
}

무난하게 통과하였다.

Union-Find는 속하거나 속하지 않는 것이 문제의 핵심일 경우에 사용할 수 있는 자료구조이다.

사용 상황에 대해서 잘 정리해두도록 하자.