[Algorithm][오답노트][이코테] 42. 탑승구

문제

공항에는 G개의 탑승구가 있으며, 각각의 탑승구는 1번부터 G번까지 번호로 구분된다. 공항에는 P개의 비행기가 차례대로 도착할 예정이며, ii번째 비행기를 1번부터 gigi(1 <= gigi <= G) 탑승구 중 하나에 영구적으로 도킹하려 한다. 이 때, 다른 비행기가 도킹하지 않은 탑승구에만 도킹이 가능하다. 또한 P개의 비행기를 순서대로 도킹하다가 만약에 어떠한 탑승구에도 도킹할 수 없는 비행기가 나오는 경우, 그 시점에서 공항의 운행을 중단한다. 공항의 관리자는 최대한 많은 비행기를 공항에 도킹하고자 한다. 비행기를 최대 몇 대 도킹할 수 있는지를 출력해라

입력

• 첫째 줄에는 탑승구의 수 G(1 <= G <= 100,000)가 주어진다.
• 둘째 줄에는 비행기의 수 P(1 <= P <= 100,000)가 주어진다.
• 다음 P개의 줄에는 각 비행기가 도킹할 수 있는 탑승구의 정보 gg(1 <= gg <= G)가 주어진다. 이는 ii번째 비행기가 1번부터 gigi번째(1 <= gigi <= G) 탑승구 중 하나에 도킹할 수 있다는 의미이다.

출력

• 첫째 줄에 도킹할 수 있는 비행기의 최대 개수를 출력해라.

느낀점

• 이 문제는 처음에 단순 구현이 떠올랐다. 그래프 카테고리에 있음에도..이 문제는 추가적인 테스트케이스가 제공되지 않아 정답임을 확인할 수는 없었다. 아마 틀렸을 것이다. 그리고 답안을 보니 너무 쉽다.
• 또한 union-find가 서로소를 판별하기 위한 알고리즘으로 대표적이지만 집합의 제한을 하기에도 사용됨을 깨닫게 해준 문제다.
• 이 문제를 다시 푼다고 해도 union-find를 떠올릴지 의아하다...
• '공항'을 root탑승구를 가진 하나의 '집합'으로 바라보고 하나의 비행기가 탑승구에 집합할 때마다 union 한다.
• "더 이상 union할 수 있는 탑승구가 없다 == 0번 탑승구에 도킹해야 한다" 가 나오면 더이상 도킹할 수 없으므로  공항의 운행을 중단한다.

#include <iostream>
#include <vector>

using namespace std;

int g, p;
int parent[100001];

int findParent(int a) {
    if (parent[a] != a) {
        parent[a] = findParent(parent[a]);
    }
    return parent[a];
}

void unionParent(int a, int b) {
    a = findParent(a);
    b = findParent(b);

    if (a < b) {
        parent[b] = a;
    }
    else {
        parent[a] = b;
    }
}

int main(void) {
    cin >> g >> p;

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

    int ans = 0;
    for (int i = 0; i < p; i++) {
        int a;
        cin >> a;
        int root = findParent(a);
        if (root != 0) {
            ans++;
            unionParent(root, root-1);
        }
        else {
            break;
        }
    }

    cout << ans << endl;


    return 0 ;
}