백준 10775번: 공항 (C++)

접근

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

10775번: 공항

전혀 감을 못잡다가 힌트의 분리집합, 즉 Disjoint-Set (Union-Find) 이용하는 것을 알고 문제를 해결할 수 있었다.

Union-Find 방식을 이용하여 a 번 게이트 입력을 받았을 때 a 의 부모 노드의 왼쪽칸(Find(a) - 1) 의 부모 노드(Find(Find(a) - 1)) 와 유니언을 이루어 주고, 만약 부모 노드가 0이라면 더이상 도킹할 수 있는 게이트가 없는 것이므로 더이상의 비행기를 카운트하지 않고 입력을 중단하면 된다.

코드

#include <iostream>

using namespace std;

#define endl '\n'
#define MAX_N 100001

int G, P;
int Parent[MAX_N];

int Find(int x) {
    if (x == Parent[x]) return x;
    return Parent[x] = Find(Parent[x]);
}

int main(int argc, char** argv) {
    // freopen 주석 처리
    freopen("input.txt", "r", stdin);

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> G >> P;
    for (int i = 1; i <= G; i++) {
        Parent[i] = i;
    }
    int total = 0;
    int p;
    for (int i = 0; i < P; i++) {
        cin >> p;
        if (Find(p) == 0) break;
        total++;
        Parent[Find(p)] = Find(Find(p) - 1);
    }

    cout << total << endl;

    return 0;
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!