[백준,c++] 10775번 - 공항

문제

10775번: 공항

 

코드

#include <iostream>
using namespace std;


int parent[100001];
int G, P, ans;


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

void union_parent(int a, int b){
    a = find(a);
    b = find(b);
    parent[a] = b;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    for(int i=0; i<=100000; i++) parent[i] = i;
    
    cin>>G>>P;
    for(int i=1; i<=G; i++){
        int gate; cin>>gate;
        
        if(find(gate) == 0) break;
        else{
            ans++;
            union_parent(find(gate), find(gate)-1);
        }
    }
    cout<<ans;
}

 

풀이

처음에 문제 이해가 잘 안 갔습니다.

공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트 중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.

이 말은 g가 3이라면 비행기가 1, 2, 3 중 한 군데 도킹할 수 있고, 만약 도킹 가능한 곳 전부가 이미 비행기로 꽉 차있다면 더 이상 아무 비행기도 도킹하지 못하고 공항을 폐쇄한다는 말입니다.

풀이 같은 경우도 다른 블로그의 풀이를 보고 해결했는데 굉장히 독특한 풀이였습니다.

도킹할 때 g번의 노드와 g-1 노드를 합치는 아이디어인데, 해결 방법은 g번 게이트부터 차례대로 도킹시키는 것입니다. g번이 차있으면 g-1, g-2, ... ,1번까지 도킹한 후 1번도 차있으면 종료합니다.

만약 g번의 노드가 0이 아니라면 도킹할 수 있다는 게이트가 적어도 한 개는 남았다는 의미가 되어 도킹시키고, 0이면 종료하는 풀이입니다.

예시를 들면 아래와 같습니다.

---

4
6
2
2
3
3
4
4

---

위와 같은 입력에서 젤 처음 초기값을 세팅하고 나면 parent 배열은 다음과 같습니다.

• parent[1] = 1, parent[2] = 2, parent[3] = 3, parent[4] = 4, parent[5] = 5, parent[6] = 6

이제 g 입력 순서대로 살펴보면 젤처음 g가 2일 경우 union_parent(2, 1)을 수행합니다. 수행하게 되면 parent[2] = 1이 됩니다.

• parent[1] = 1, parent[2] = 1, parent[3] = 3, parent[4] = 4, parent[5] = 5, parent[6] = 6

다음 입력도 g가 2가 들어오게 됩니다. union_parent(1, 0)을 수행합니다. 수행하게되면 parent[1] = 0이 됩니다.

• parent[1] = 0, parent[2] = 1, parent[3] = 3, parent[4] = 4, parent[5] = 5, parent[6] = 6

다음은 g가 3이 들어오게 됩니다. union_parent(3, 2)을 수행합니다. 수행하게되면 parent[3] = 2가 됩니다.

• parent[1] = 0, parent[2] = 1, parent[3] = 2, parent[4] = 4, parent[5] = 5, parent[6] = 6

다음도 g가 3이 들어오게 됩니다. find(3) = 0이 됩니다. 따라서 종료합니다.