백준 10775번. 공항(c++) / 유니온파인드

아이디어가 생각나지 않아 다른 분의 아이디어를 참고하여 유니온파인드로 구현했다.

 

핵심 아이디어는 3번 게이트로 들어오게 되면, 3->2를 가리키도록 union해주어야 한다.

따라서, 다시 한 번 3번 게이트로 다른 비행기가 들어오면 바로 3의 Parent인 2에 넣어줄 수 있게 된다.

만약 Parent값이 게이트 범위 안에 있지 않다면, 바로 공항은 폐쇄된다.

 

 

코드 첨부

// 공항
#include <iostream>
#include <vector>
using namespace std;
 
int g, p, n;
vector<int> airplane;
int num = 0;
int connect[100001] = {0, }; // 유니온파인드
 
int find(int x){
    if(connect[x] == x){
        return x;
    }else{
        return connect[x] = find(connect[x]);
    }
}
 
int main()
{
    cin>>g>>p;
    for(int i=1; i<=g; i++){
        connect[i] = i;
    }
    for(int i=0; i<p; i++){
        cin>>n;
        airplane.push_back(n);
    }
 
    for(int i=0; i<airplane.size(); i++){
        int a = find(airplane[i]);
        if(1<=a && a<=g){
            // a와 a-1을 연결해준다.
            connect[a] = a-1;
            num++;
        }else{
            break;
        }
    }
    
    cout<<num<<"\n";
    return 0;
}

 

문제 첨부

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

10775번: 공항