백준 10775번 : 공항 - dis-joint set , Union&Find C++

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

10775번: 공항

1. 문제설명 및 접근방법[알고리즘]

 

g번 게이트가 이미 도킹 되었으면 g-1번 게이트가 비어있는지 확인하고

g-1번 게이트도 이미 도킹 되어있으면 g-2번 게이트를 확인해야 합니다.

이런 식으로 g-k 가 1번까지 갔을 때 1번마저 도킹이 되어있다면 더이상 도킹을 할 수 없습니다.

 

이걸 구현하기 위해서

dis-joint set(Union&Find) 알고리즘을 이용하여

현재 k번이 도킹되었다면 k와 k-1를 Union해주고 k-1이 루트가 되게 해줍니다.

그러면 다음에 Find(k)를 했을 때 아직 사용하지 않은 게이트인 k-1 번 게이트를 얻을 수 있습니다.

 

g번 게이트에 도킹할 때마다 Find(g)와 FInd(g)-1을 Union 해주면서

도킹을 할 수 없을 때까지 반복하는 코드를 구현합니다.

 

 

 

---

 

2.문제풀이 코드 C++

#include <bits/stdc++.h>
using namespace std;

int g,p,unf[100001], arr[100001];

int Find(int x) {
	if (unf[x] < 0) return x;
	return unf[x] = Find(unf[x]);
}


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

	if (a == b) return;
	else if (a < b) {
		unf[b] = a;
	}
	else {
		unf[a] = b;
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	memset(unf, -1, sizeof(unf));
	cin >> g >> p;

	int cnt = 0;
	for (int i = 0; i < p; i++) {
		cin >> arr[i];
	}

	for (int i = 0; i < p; i++) {
		int a = Find(arr[i]);
		
		if (a >= 1) {
			Union(a, a - 1);
			cnt++;
		}
		else {
			cout << cnt << '\n';
			return 0;
		}
	}

	cout << cnt << '\n';

	return 0;
}

백준 10775번