[백준] 공항 10775번 (c++)

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

 

풀이 방법

처음에는 그리디한 방법으로 자신이 연결 가능한 가장 큰 게이트부터 차례대로 1씩 줄이며 가능한 곳에 연결하는 방법을 생각했지만, 이는 계산해 보니 시간초과가 난다.

그러므로 다른 방법이 있어야 하는데 도저히 생각하지 못했다. 다른 사람의 풀이를 보니 유니온파인드를 사용해서 풀이하고 있었다.

자신의 부모와 자신의 부모 -1한 값을 유니온 하는 방식으로 풀이하면 된다. 그러다 자신의 부모가 0이 되는 값이 발생하면 종료를 해주면 된다. 

 

#include <iostream>

using namespace std;

int g, p;
int gate[100001];
int parents[100001];

int find(int a) {
	if (a == parents[a]) return a;
	parents[a] = find(parents[a]);
	return parents[a];
}

void union_f(int a, int b) {
	int parents_a = find(a);
	int parents_b = find(b);
	if (parents_a == parents_b) return;
	if (parents_a < parents_b) parents[parents_b] = parents_a;
	else {
		parents[parents_a] = parents_b;
	}
	return;
}



int main() {
	cin >> g >> p;

	for (int i = 0; i <= 100000; i++) {
		parents[i] = i;
	}

	int answer = 0;
	for (int i = 0; i < g; i++) {
		cin >> gate[i];
		int a = find(gate[i]);
		if (a == 0) break;
		else {
			answer++;
			union_f(a - 1, a);
		}
	}
	cout << answer << '\n';
	return 0;
}