[백준 C++] 10775번: 공항

1. 문제

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

10775번: 공항

 

2. 알고리즘 분류

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

 

3. 소스 코드

#include <iostream>
#define MAX_G 100005

using namespace std;

int G, P;
int g[MAX_G];
int airport[MAX_G];
int parent[MAX_G];

int Find(int a)
{
	int pA = parent[a];

	if (pA == a)
		return a;

	return parent[a] = Find(pA);
}

void Union(int a, int b)
{
	int pA = Find(a);
	int pB = Find(b);

	if (pA <= pB)
		parent[pB] = pA;
	else
		parent[pA] = pB;
}

int main()
{
	// I/O 속도 향상
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int ans = 0;

	for (int i = 0; i < MAX_G; i++)
		parent[i] = i;

	// G : 게이트의 수, P : 비행기의 수
	cin >> G;
	cin >> P;

	// g[i] : 1번부터 g[i]번째 게이트 중 하나에 도킹
	for (int i = 1; i <= P; i++) {
		int val;
		cin >> val;

		val = Find(val);	// 비행기 도킹 가능한 게이트가 있는지 확인

		if (val == 0) break;	// 비행기 도킹이 더이상 불가능하면 종료

		Union(val, val - 1);	// 비행기 도킹 체크
		ans++;
	}

	// 정답 출력
	cout << ans;

	return 0;
}

 

4. 유용한 문법 및 알고리즘

1) 분리 집합(Union-Find)

1. 노드들을 그룹을 지을 때 사용하는 알고리즘

int parent[MAX_G];

int Find(int a)
{
	int pA = parent[a];

	if (pA == a)
		return a;

	return parent[a] = Find(pA);
}

void Union(int a, int b)
{
	int pA = Find(a);
	int pB = Find(b);

	if (pA <= pB)
		parent[pB] = pA;
	else
		parent[pA] = pB;
}