백준 10775 공항 (C++)

10775번: 공항

분리 집합을 이용한 문제이다. 문제에서의 설명에 의하면 1부터 주어진 입력 g까지 사이의 게이트 중 하나에 영구적으로 도킹을 하고 이후 입력으로 주어진 g까지의 게이트가 모두 차있으면 종료를 한다고 적혀있다. 즉 현재 도킹되어있는 게이트의 여부를 확이해주어야 한다. 이를 분리 집합을 이용해주었다. 우선 게이트를 나타내는 p 배열을 자기자신을 가지도록 초기화 해주었다. 그리고 비행기 수만큼 반복문을 돌면서 해당 게이트의 값을 확인하여 조건에 따라 게이트 값을 변경해주었다. 게이트를 확인하는 방식은 간단하다. 1~4 까지의 게이트의 남은 수는 p[4]를 나타낸다. 처음 g=4일 경우 맨 뒤 게이트부터 도킹을 해주고 p[3]과 union을 해준다. 이유는 1~3 까지의 남은 게이트 수와 동기화를 해주기 위해서라고 생각하면 된다. 이런 방식으로 반복문을 돌면서 만약 p[g]가 0이 나올 경우 남은 게이트 수가 없다고 판단하고 반복문을 종료한뒤 카운트한 값을 출력해주었다.
생각보다 어려웠던 문제였다. 문제를 이해하는 것까진 어렵지 않았는데 단순 완전 탐색으로 구현을 할 경우 시간 초과가 날 것이 뻔했기에 남은 게이트 수를 어떻게 관리해야 할지 도무지 생각이 나지 않았다. 블로그를 참고하여 아이디어를 알아내어 문제를 해결하였는데 분리 집합을 이러한 방식으로도 사용할 수 있다는 점에서 놀라웠다. 분리 집합을 이용하는 이러한 방식에 대해서도 잘 인지해두어야 겠다.

#include <iostream>
#include <vector>

using namespace std;

int G, P, result = 0;
vector<int> v;
int p[100001];

int findParent(int a) {
	if (p[a] == a) return a;
	else return p[a] = findParent(p[a]);
}

void unionParent(int a, int b) {
	a = findParent(a);
	b = findParent(b);

	if (a != b) p[a] = b;
}

void solution() {
	for (int i = 0; i <= G; i++) {
		p[i] = i;
	}

	for (int i = 0; i < P; i++) {
		if (!findParent(v[i])) break;
		else {
			result++;
			unionParent(findParent(v[i]), findParent(v[i]) - 1);
		}
	}

	cout << result;
}

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

	cin >> G;
	cin >> P;

	int g;
	for (int i = 0; i < P; i++) {
		cin >> g;
		v.push_back(g);
	}

	solution();
	
	return 0;
}