[백준/Baekjoon] 10775 공항 C++ :: Union-Find

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

10775번: 공항

---

1. Logic

일단 문제를 이해하는데 너무 시간이 오래걸렸다.. ㅋㅋㅋㅋ 이해가 안가서 알고리즘 분류를 봤는데 유니온파인드여서 대충 풀이는 어떻게 할지 떠올랐지만 확실히 이해가 안가서 다른 블로그들을 참고했다.

 

일단 우리는 1번부터 g번까지 게이트가 있고 여기에 도킹을 시켜야한다. 배열은 0부터 시작하기 때문에 만약 1번 게이트에 도킹을 하면 0번 배열에 비행기를 위치시킨다.(merge(find(a), find(a) -1)) 이렇게 되면 비행기를 도킹시키면 어느 한 루트노드로 모이게 될 것이고, 각각 도킹할 비행기의 루트노드를 검사하여 공간이 있으면 허가하고 만약  find한 값이 0이 나오면 공항을 닫아버리면 된다.

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int g, p;
int ans = 0;

int parent[100001];

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

    return parent[x] = find(parent[x]);
}

void merge(int x, int y) {
    x = find(x);
    y = find(y);

    if(x == y) return;

    if(x < y) parent[y] = x;
    else parent[x] = y;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> g >> p;

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

    for(int i = 0; i < p; i++) {
        int a;
        cin >> a;

        if(find(a) == 0) break;
        else {
            ans++;
            merge(find(a), find(a) - 1);
        }
    }

    cout << ans;
}

 

 

---

3. Feedback

문제를 이해하는데 너무 어려웠다. 

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90