[백준 10775] 공항 (C++)

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

문제

---

오늘은 신승원의 생일이다.

박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.

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

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

신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

 

입력

---

첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 10⁵)가 주어진다.

두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 10⁵)가 주어진다.

이후 P개의 줄에 g_i (1 ≤ g_i ≤ G) 가 주어진다.

 

출력

---

승원이가 도킹시킬 수 있는 최대의 비행기 수를 출력한다.

 

문제 풀이

---

union-find를 이용한 문제.

각 비행기들은 g_i번 게이트까지의 도킹 가능한 게이트 중 i가 가장 큰 수의 게이트에 도킹해야 최대로 비행기를 도킹시킬 수 있다.

각 게이트에 대해 i번째 게이트까지 현재 도킹 가능한 게이트 중 i가 가장 큰 수를 저장하는 배열을 만들어 각 인덱스를 i로 초기화한다. 입력받은 게이트에 대해 부모를 찾고, 부모에 해당하는 값과 그 값-1 게이트를 union시킨다. 만약 부모가 0이라면 도킹시킬 수 있는 게이트가 없으므로 반복문을 빠져나온다.

 

아래는 코드.

#include <iostream>
using namespace std;
int* maxGates;

int findParent(int x)
{
	if (maxGates[x] == x)
	{
		return x;
	}
	else
	{
		maxGates[x] = findParent(maxGates[x]);
		return maxGates[x];
	}
}

void merge(int x, int y)
{
	int parentX = findParent(x);
	int parentY = findParent(y);
	maxGates[parentY] = parentX;
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N, M;
	int gateNum;
	int dockingAirplanes = 0;
	cin >> N>>M;
	maxGates = new int[N+1];
	for (int i = 0; i < N+1; i++)
	{
		maxGates[i] = i;
	}
	for (int i = 0; i < M; i++)
	{
		cin >> gateNum;
		int currentMaxGate = findParent(gateNum);
		if (currentMaxGate == 0)
		{
			break;
		}
		else
		{
			merge(currentMaxGate-1, currentMaxGate);
			dockingAirplanes++;
		}
	}
	cout << dockingAirplanes << "\n";
	return 0;
}