[백준 10775번] [Union-Find] 공항

사실상 이 문제를 풀기위한 알고리즘 및 자료구조를 학습하고 문제를 풀게 되었다.

 

특히 이 문제를 풀기 위해서 유니온 파인트 자료구조가 필요한데, 해당하는 내용은 종만북 2권 25.1에 나와있으니 잘 복습하도록 하자.

 

이 문제를 상호 배타적 집합으로 간주해도 되는 이유를 이해하는 것이 훨씬 더 중요하다.

 

사실상 도킹이 되거나 안되거나 둘 중 하나의 상황으로 이어지므로 이를 상호적 배타 집합으로 이해할 수 있다.

이러한 측면에서 유니온 파인드 자료구조를 활용하는 느낌으로 이해하면 될 듯 싶다.

 

이 문제는 자주 복습하면서 종만북을 참고하도록 하자.

 

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

using namespace std;

int G, P;

struct DisjointSet{
    vector<int> parent;
    // Constructor
    DisjointSet(int N) : parent(N){
        for(int i = 0 ; i < N; i++){
            parent[i] = i;
        }
    }
    // U가 속한 트리의 루트를 반환
    int find(int u){
        if(parent[u] == u) return u;
        else{
            return parent[u] = find(parent[u]);
        }
    }

    // U와 V가 속한 트리를 병합
    void merge(int u, int v){
        u = find(u);
        v = find(v);
        if(u == v) return;
        // u가 무조건 더 작게끔
        if(u > v) swap(u, v);
        parent[v] = u;
        return; 
    }
};

int main(void){
    cin >> G;
    cin >> P;
    
    DisjointSet Disjoint(G + 1);

    for(int i = 0; i < P; i++){
        int temp;
        cin >> temp;
        int check_num = Disjoint.find(temp);
        if(check_num == 0){
            cout << i << "\n";
            return 0;
        }
        Disjoint.merge(check_num, check_num -1);
    }

    cout << P << "\n";

    return 0;
}

무난하게 통과하였다.