BOJ - 10775번 공항(C++)

문제 출처: https://www.acmicpc.net/problem/10775

문제 난이도

Gold 1

문제 접근법

Gate와 Plane은 각각 다른 집합이고, Plane이 Gate에 도킹하면 영구적으로 도킹하기 때문에 추후에 다른 비행기가 도킹하려고 하면 안된다.
그렇기 때문에, Union-Find 알고리즘을 사용해서 Gate라는 전체 집합에서 구성 원소들이 겹치지 않도록 부분 집합을 구성한다.

통과 코드

#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;

int gate[100001];

int Find(int v) {
	if (gate[v] == v) return v;
	return gate[v] = Find(gate[v]);
}

void Union(int a, int b) {
	int x = Find(a);
	int y = Find(b);
	if (x != y) {
		gate[x] = y;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int G, P;
	cin >> G >> P;
	vector<int> plane(P);
	for (int i = 0; i < P; i++) {
		cin >> plane[i];
	}
	for (int i = 1; i <= G; i++) {
		gate[i] = i;
	}
	int cnt = 0;

	for (int i = 0; i < plane.size(); i++) {
		int dockingGate = Find(plane[i]);
		if (dockingGate != 0) {
			Union(dockingGate, dockingGate - 1);
			cnt++;
		}
		else {
			break;
		}
	}
	cout << cnt << "\n";
	return 0;
}

기타

이 문제가 짧은데 난이도가 있는 편이라 왜인가 했더니 문제를 보고 알고리즘을 짜기가 쉽지가 않다. 만약 짠다고 해도 틀리는 경우가 있어 완전하게 푼다고 할수도 없다.
큐를 이용해서 풀었는데 1초 남기고 68%에서 틀렸습니다가 떴다. 그 외로 점화식도 세워보려고 했으나 잘 안되서 다른 풀이를 참고하게 됐다.
문제를 보고 Union-Find 알고리즘을 떠오르기가 쉽지가 않은데 서로소인 집합과 집합에서 부분 집합을 찾는다고 하면 이 알고리즘을 떠올려봐야겠다.