[백준 알고리즘] 10775번: 공항

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

문제

문제

오늘은 신승원의 생일이다.

박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.

공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.

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

신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

입력

첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 105)가 주어진다.

두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 105)가 주어진다.

이후 P개의 줄에 gi (1 ≤ gi ≤ G) 가 주어진다.

출력

승원이가 도킹시킬 수 있는 최대의 비행기 수를 출력한다.

풀이

이 문제 역시 유니온 파인드로 풀어야했는데, 기존의 유형과는 조금 달리 더 생각해야하는 문제였다. 결국 혼자 힘으로는 풀지 못하고 블로그들을 보면서 풀게 되었다. 이 문제에서 사용해야하는 유니온 파인드 전략은, 입력받은 게이트의 부모를 그 바로 이전 번호의 게이트를 유니온 연산으로 합쳐주는 것이다. 예를 들어, 3이 입력으로 주어진다면, 3과 2를 인자로 유니온 연산을 수행한다. 이렇게 연산을 진행하면, 다음번 3이 입력으로 들어왔을 때는, 3의 부모인 2에 새로운 비행기를 도킹 하고, 해당 게이트의 부모게이트를 1번 게이트로 만들게 된다.

이때 핵심이 되는 부분은 게이트들의 부모게이트가 1번 게이트인 경우이다. 이 말은 즉, 1번 게이트에 비행기가 도킹되면 1번 게이트는 존재하지 않는 0번 게이트를 부모게이트로 가지게 되기 때문에 더 이상 도킹할 수 있는 자리가 존재하지 않다는 것을 의미한다. 따라서 0번 게이트가 등장할 때까지 입력 g의 부모게이트와 그 게이트의 -1 번째 게이트를 계속해서 유니온 연산으로 합쳐주면 도킹이 가능한 최대 비행기의 개수를 알 수 있다.

코드

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

using namespace std;

int parent[1000001];

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

void merge(int a, int b) {
    a = findRoot(a);
    b = findRoot(b);

    parent[a] = b;
}

int main() {
    int G, P;
    cin >> G >> P;

    for (int i = 1; i <= G; i++) {
        parent[i] = i;
    }

    int count = 0;
    int currGate;
    int parentGate;
    for (int i = 0; i < P; i++) {
        cin >> currGate;
        if ((parentGate = findRoot(currGate)) == 0) break;
        merge(parentGate, parentGate - 1);
        count++;
    }

    cout << count;
}