BOJ(백준) 10775 - 공항

---

아이디어

처음에 접근을 공항과 비행기 노드를 따로 나눠서 생각해보았다. 어떤 식으로 데이터를 정의하고, 자료구조에 담을 것인가 생각하다가 보니, 이 아이디어는 유니온파인드 스럽지 않은 문제를 유니온파인드로 설정하는 아이디어였다. 문제의 까다로운 조건들을 보면 merge와 find를 어떤 식으로 활용하라는 힌트가 주어져 있다. 

★★

도킹을 하면 그 노드는 방문하지 못하게끔 되고, parent설정을 통해 방문하지 못하게된 노드를 다시 방문할 때는 parent로 유도한다. 방문과 동시에 merge를 통해 parent를 다시 설정하게 되고, 그 다음 번 방문을 위해 경로압축도 진행된다. 

 

---

점검해볼 사항

- 유니온파인드를 트리의 관점에서 바라보기

- 경로압축을 통해 이런 문제 처럼 시간절약을 할 수 있다.

- find와 merge의 활용

---

시간복잡도

O(P) : P를 find하고 다음 번 위치까지 merge지정해두기 때문에 대략 매번 O(1)의 연산을 하게 되고, 그것을 P번 반복한다.

---

https://github.com/jongwuner/Algorithm/blob/master/BOJ/10775.cpp

#include<iostream>
#include<vector>
using namespace std;
vector<int> p;
int find(int idx) {
    if (p[idx] < 0) return idx;
    return p[idx] = find(p[idx]);
}
int main() {
    int N, M, ans = 0;
    scanf("%d%d", &N, &M);
    p.resize(N + 1, -1);
    for (int i = 0, node; i <= N; i++) {
        scanf("%d", &node);
        node = find(node);
        if (!node) break;
        p[node] = node - 1;
        ans++;
    }
    printf("%d\n", ans);
    return 0;
}