[Baekjoon] 백준 10775번: 공항 (c++)

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

10775번: 공항

 

Union Find문제에 익숙해져서 그런지 솔루션을 찾으면 푸는데 크게 어려움은 없었다.

다만 문제 이해가 오래 걸릴뿐...

내가 푼 방법은 이렇다

게이트들을 모두 노드라고 생각하고,

1. 입력 g에 대하여 루트노드를 찾는다. Find(g)

2. 루트 노드 g_parent에 대하여, g_parent의 차선책을 g_parent-1로 지정한다. Union(g_parent, g_parent-1)

      2.1  a, b로 주어진 노드들에 대하여 각각의 루트노드를 찾아 지정해준다. parent[a] = b

      2.2  Union이 한번 이루어지면 비행기가 정상적으로 도킹되었다는 의미이므로 cnt++을 해준다.

3. 만약 g_parent가 0이라면 for문을 중지하고, 현재 cnt를 출력한다.

 

 

---

코드(c++)

#include <string>
#include <vector>
#include <iostream>
using namespace std;
#define MAX 100001

int cnt=0;
int parent[MAX] = {0,};
int Find(int x){
    if(x == parent[x]) return x;
    
    int p = Find(parent[x]);
    parent[x] = p;
    return p;
    
}
void Union(int a,int b){
    a = Find(a); //또 2가들어오면 2의 부모를 찾아 (1)
    b = Find(b);
    
    parent[a] = b;
    cnt++;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
   
    int G, P, g;
    
    cin >> G >> P;
    for(int i=1;i<=G;i++)parent[i] = i;
    for(int i=0;i<P;i++){
        cin >> g;

        int g_parent = Find(g);
        if(g_parent == 0)break;
        Union(g_parent, g_parent-1);
    }
    
    cout << cnt;
    
    return 0;
}