백준 10775번: 공항

 

 

Union-find를 활용한 문제이다.

다음은 Union-find를 공부하기에 좋은
기본적인 문제다.

 

*** Union-find 개념 ***

https://gimmesome.tistory.com/34?category=1103655

[1주차] Union-find

 

 

 

 

 

 

 

처음에 방향을 잡는데 시간이 좀 걸렸다.
나름 잘돌아가는 게 다행인 문제....

 

 

 

 

 

 

 

중요 포인트 몇가지만 생각하면 된다. 

 

1. g를 입력 받으면 1~g까지의 게이트 중에서 하나의 게이트에 도킹해야한다. g~1로 역순으로 찾는 것이 쉽다. 따라서 g에 도킹이 가능하면 다음에 있을 g와의 도킹 시도에서 그 다음 대안인 g-1를 찾아갈 수 있게 g-1과 g를 merge하는 방식으로 한다. 
2. 여기서 merge는 find(g-1)로 g-1의 부모노드를 찾아서 arr[g]에 넣는다. g-1이 이미 도킹된 경우 1번처럼 merge되어서 부모노드가 있을 것이다.
3. find는 기존 union-find에서 했던 findParent 함수를 그대로 가져다 쓰면된다. 배열값이 -1(초깃값)인 게이트가 발견되면 도킹이 안되었다는 것이기 때문에 그 게이트를 return 한다. 
4. find(g)로 리턴받은 값(도킹 가능한 게이트)이 0이면 도킹할곳이 없다는 뜻이다. g부터 -1씩 해서 0까지 부모노드인지 찾는거기 때문에 0이면 그전에 1~g는 모두 부모노드가 아니였다는 것이기 때문.
5. find(g)로 리턴받은 값(도킹 가능한 게이트)이 0이 아니면 cnt(도킹된 게이트 수)를 ++하고 merge한다. 

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int G, P, cnt;
int arr[100001];

int find(int num) {
	if (arr[num] < 0)
		return num;
	int parent = find(arr[num]);
	arr[num] = parent;
	return parent;
}

void merge(int empty) {
	arr[empty] = find(empty - 1);
}

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);	//cin 실행속도 향상

	cin >> G >> P;

	for (int i = 0; i <= G; i++) {
		arr[i] = -1;
	}

	for (int i = 1; i <= P; i++) {

		int plane;
		cin >> plane;

		int empty = find(plane);
		if (empty == 0)
			break;
		else {
			cnt++;
			merge(empty);
		}
	}

	cout << cnt << endl;

	return 0;
}