[백준] 10775번 - 공항 (서로소 집합 알고리즘 활용)

[백준] 공항 (서로소 집합 알고리즘 활용)

[링크] https://www.acmicpc.net/problem/10775

💎 문제 조건과 설명

문제 조건과 설명은 위의 링크를 참조 부탁드립니다.

🚀 생각한 아이디어

인풋으로 탑승구의 수 G와 비행기의 수 P가 주어지고, 다음 P개의 줄에 i번째 비행기의 도킹 가능한 탑승구 정보가 주어집니다.

이 문제는 문제의 말 뜻과 상황을 먼저 잘 이해해야 될 것 같습니다..

예를 들어 아래와 같이 인풋이 주어졌을 경우,

1
2
3
4
5

4
3
4
1
1

4는 탑승구의 수, 3은 순서대로 도킹할 비행기의 수입니다.

그리고 그 밑에 4, 1, 1은 각각

• 첫 번째 비행기는 1번부터 4번까지의 탑승구 중 하나에 도킹 할 수 있다. = 1~4번 탑승구 중 한 군데 가능
• 두 번재 비행기는 1번부터 1번까지의 탑승구 중 하나에 도킹 할 수 있다. = 1번 탑승구만 가능
• 세 번째 비행기는 1번부터 1번까지의 탑승구 중 하나에 도킹 할 수 있다. = 1번 탑승구만 가능

라는 의미이고, 도킹은 첫 번째 비행기부터 순서대로 진행해야 합니다.

그리고 문제에서 다른 비행기가 도킹하지 않은 탑승구에만 도킹할 수 있다고 했으므로, 각 탑승구에는 최대 1개의 비행기만 도킹이 가능하다는 의미입니다.

위 인풋에서 첫 번째 비행기는 1~4번 탑승구 중 한 군데가 가능한데, 만약 가장 먼저 1번 탑승구에 도킹을 해버린다면, 그 다음 두 번째 비행기는 1번 탑승구만 가능한데 이미 첫 번째 비행기가 그곳에 도킹했으므로 어디에도 도킹할 탑승구가 없고, 그대로 종료되어 버릴 것입니다.

그러므로 최대한 많은 비행기를 도킹하려면 가능한 범위의 탑승구 중에서 가장 마지막부터 확인하면서 채워넣으면 되겠습니다. 그리고 이미 그 탑승구에 비행기가 있다면, 그 이전 탑승구를 확인하는 식으로 찾아나가면 됩니다.

그 과정을 서로소 집합 알고리즘을 활용하여 구현할 수 있습니다.

• 각 탑승구를 노드로 생각해 보겠습니다. 그리고 0번 탑승구는 없으나 1번의 부모 역할을 위해 있다고 가정합니다.4, 1, 1 순으로 인풋이 주어졌으므로 4번 탑승구에 비행기가 있는지 확인합니다. 그 방법은 4번이 다른 노드와 연결되어 있는지를 보면 됩니다. 초반에는 아무것도 연결되지 않았으므로 parent[4] = 4 이므로 첫 번째 비행기를 4번에 도킹하고, 4를 3번 노드와 union 합니다. 그러면 parent[4] = 3이 됩니다.
• 두 번째 비행기를 1번에 도킹하기 위해 확인합니다. parent[1] = 1 즉 자기 자신일 것이므로 1번에 도킹하고 1번 노드를 0번에 합칩니다. 그러면 parent[1] = 0 이 됩니다.
• 세 번째 비행기를 1번에 도킹하기 위해 확인합니다. parent[1] = 0 입니다. 즉, 도킹할 수 없습니다. 이전 것을 타고 타면서 부모를 계속 살펴보고 최종적으로 0이 나오면 아무데도 도킹할 곳이 없다는 뜻입니다.
• 따라서 **이 인풋에서는 비행기를 최대 2대만 도킹할 수 있습니다. **도킹할 곳이 없으면 그 즉시 프로그램은 종료됩니다.

• 물론 위의 예시는 종료된 것이지만, 여기에 다른 비행기가 또 한대 들어온다고 상황을 가정해 보겠습니다.

만약 첫 번째, 두 번째 비행기가 각각 도킹된 상황에서 새로운 비행기의 탑승구 정보가 4 라고 주어졌다고 가정해 보겠습니다. 이 때는, parent[4] = 3 입니다. 따라서 3번 탑승구에 도킹할 수 있습니다. 그리고 3번 노드는 이전 노드인 2번에 합쳐지고, parent[3] = 2 가 될 것입니다.

• 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#include <iostream>
#include <algorithm

using namespace std;

int link[100001];
int sizes[100001];

int find(int v) {
	if (link[v] == v) return v;
	return link[v] = find(link[v]);
}

void unite(int a, int b) {
	// 먼저 a와 b의 대푯값을 찾는다.
	a = find(a);
	b = find(b);

	// 인자에 차례대로 v, v-1로 들어오는 것으로 가정
	link[a] = b;
}


int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);

	int G, P;
	cin >> G >> P; // 게이트의 수, 비행기의 수
	
	// 초기화
	for (int i = 1; i <= G; i++) {
		link[i] = i;
		sizes[i] = 1;
	}

	int p_gi, gi, cnt = 0;
    
	for (int i = 0; i < P; i++) {
		cin >> gi;
		p_gi = find(gi);
		if (p_gi != 0) {
			unite(p_gi, p_gi - 1);
			cnt += 1;
		}
		else
			break;
	}

	cout << cnt;
	return 0;
}