백준 10775: 공항

문제 요약

공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.

공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.

비행기를 최대 몇 대 도킹시킬 수 있는가?

문제 분류

• 자료 구조
• 그리디 알고리즘
• 분리 집합

문제 풀이

비행기를 공항에 최대한 많이 도킹시키는 문제이다. 여기서 각 비행기당 g값이 존재하는데, 이것은 이 비행기가 1~g번째의 게이트에만 도킹 가능하다는 뜻이다.

즉, 되도록 큰 게이트에 도킹하는 것이 좋을 것이다. 도킹되어 사용된 게이트를 유니온 파인드 집합으로 처리함으로써 해당 게이트를 비활성화한다. 여기서 각 집합의 최상위 노드는 자기 자신을 가리키게 만든다. 그렇게 하면 각 노드에서 사용할 수 있는 가장 큰 수가 나오게 된다. 즉, find(g)를 통해 g보다 작은 수 중 도킹 가능한 게이트 번호가 나오는 것이다.

가령 g가 5라고 하자. 5가 사용되지 않은 경우, find(5) = 5가 되어 사용가능하다는 뜻이다. 여기서 5를 집합으로 처리하는데, 5의 부모를 5보다 작으면서 가장 큰 노드로 맞춰주는 것이다. 즉 find(5)를 통해 5이하의 수 중 유효한 가장 큰 수를 구하는 것이다. 여기서 5를 사용하였으므로 p[find(5)] = find(find(5) - 1)를 해준다. 이 의미는 5의 부모노드를 5보다 1작은 노드의 부모노드로 만드는 것이다. 여기서 4가 유효한 경우에는 4가 되겠지만, 4가 유효하지 않은 경우는 결국 4의 최상위 노드를 똑같이 가르키게 된다. 이 부모노드가 0인 경우는 1~g까지의 게이트가 모두 사용되었음을 의미하므로 반복문을 빠져나오고, 지금까지의 개수를 출력한다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

int p[100001];

int find(int n) {
	if (p[n] == n) return n;
	p[n] = find(p[n]);
	return p[n];
}

int main()
{
	int g, m, in, cnt = 0;
	scanf("%d%d", &g, &m);
	for (int i = 1; i <= g; i++)
		p[i] = i;
	while (m--) {
		scanf("%d", &in);
		if (find(in) == 0) break;
		else {
			cnt++;
			p[find(in)] = find(find(in) - 1);
		}
	}
	printf("%d", cnt);
}