이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 9 번째 글 입니다.
목차
골드2 : 유니언 파인드 문제이다.
생각
이런 문제는 정말 비행기가 온다고 생각하고 푸는 것이 가장 좋은 것 같다. 그러니까 모든 문제는 시뮬레이션을 제대로 하는 것이 중요.. 총 5개의 게이트가 있다고 하자. 그 때, 4번으로 비행기가 들어온다. 그럼 4번에 배정하는 것이 맞다. 그런데 또 4번으로 들어온다. 이 문제는 4번 보다 작은 게이트에만 비행기가 들어올 수 있으므로 들어갈 수 있는 게이트는 1, 2, 3이다. 그런데, 문제 특징 상 원하는 게이트보다 작은 부분에만 들어갈 수 있으므로 가장 많은 비행기를 넣기 위해서는 원하는 게이트에서 작은 숫자를 가진 게이트 중, 숫자가 가장 큰 게이트에 들어가는 것이 최선이다.(응?) 이해를 위해 표를 그려보자.
| gate | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 |
이 상황에서 3번 게이트로 들어올 경우 두가지 그림이 가능하다.
| gate | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 1 | 0 | 0 | 1 | 0 |
| gate | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 0 |
1번 표의 경우, 만약 1번으로 들어오는 비행기가 있다고 하면, 이 비행기는 이미 게이트가 차 있으므로 들어가지 못한다. 그래서 총 숫자는 2이다. 2번 표에서는 1번 게이트가 비어있으므로 비행기를 댈 수 있다. 그 결과 정답은 3이다. 이렇게, 비행기가 들어오는 방법은 원하는 게이트보다 작거나 같은 게이트 중 비어있는 게이트에서 가장 큰 숫자를 가진 게이트 순서로 도킹해야한다.
유니온 파인드
위에서 생각한 것은, 대안 게이트를 찾는 방법이다. 그런데 생각해보면, 이 대안 게이트는 그래프로 볼 수 있다.
gate : 1, 2, 3, 4, 5
airplain : 4, 4, 3, 1
위와 같은 순서로 비행기가 들어온다고 했을 때의 그림을 보자.
airplain 4
airplain 4
airplain 3
airplain 1
이 과정에서, 신경써주어야 하는 것은, 해당 게이트의 대안 게이트의 번호가 무엇인지이다! 무조건 처음에는 비행기가 왔을 때, 자신의 게이트에 넣는 것은 확정이므로, 처음 도킹 위치의 초기값은 자기 자신의 게이트 이다. 이제 비행기가 들어오면서, 어떠한 방법으로 이것을 업데이트 해줄지 고민하면 된다.
대안 게이트 합치기
기본적으로 대안 게이트의 위치는 나보다 하나 작은 녀석의 게이트이다. 하지만 그 위치에도 이미 도킹이 되어 있다면, 그 녀석의 대안 게이트를 또 찾아야 한다. 그러므로 대안 게이트를 찾아서 업데이트 할 때는 나보다 작은 녀석을 기반으로 하되, 그녀석의 최종적인 대안 게이트를 찾아야 한다. 유니온 파인드 알고리즘에서 이 대안 게이트는 조상에 치환되는 개념으로 볼 수 있다. 결국은 조상을 찾아서, 그 조상으로 업데이트를 진행해야 한다.
종료조건은 간단하다. 문제에서 보여주듯 원하는 게이트보다 작은 게이트들이 다 도킹이 된 상태면 종료한다. 이 조건은, 알고리즘 상에서 대안 게이트의 번호가 0이 되는 것과 동치이다. 0번 게이트는 없으므로 도킹할 수 없다.
알고리즘
- 초기 게이트의 위치를 대안 게이트의 번호를 자기자신의 게이트를 가리키도록 한다.
- 비행기가 들어올 때, 대안 게이트를 찾는다.
- 대안 게이트를 찾으면, 대안 게이트에 비행기가 도킹했다고 생각하고 도킹한 비행기의 숫자를 늘린다.
- 대안 게이트에 비행기가 들어왔으므로, 방금 도킹한 비행기의 대안 게이트를 찾는다.
- 만약, 대안 게이트의 번호가 0인 경우 현재까지 도킹한 비행기를 출력하고 종료한다.
Code
#include <iostream>
using namespace std;
int n, m;
int parent[100001];
int ans = 0;
int find(int gate){
if (gate == parent[gate]){
return gate;
}
return parent[gate] = find(parent[gate]);
// 탐색하는 과정에서 있었던 대안 게이트를 최종 값으로 업데이트한다.
}
// 게이트의 최종 대안 게이트로 업데이트 한다.
void unite(int x, int y) {
x = find(x);
y = find(y);
parent[x] = y;
}
int main(){
cin >> n >> m;
for (int i = 1; i <= n; i++) {
parent[i] = i;
}
for (int i = 0; i < m; i++) {
int command;
cin >> command;
int empty_gate = find(command);
if (empty_gate == 0) {
break;
}
ans++;
unite(empty_gate, empty_gate-1); // 기본적으로 나보다 하나 작은 게이트와 합친다.
}
cout << ans << '\n';
return 0;
}