[백준] 10775번 공항 [C++]

 

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

10775번: 공항

---

---

접근 방식

유니온 파인드(분리 집합)을 사용하여 문제를 해결하였다.

현재 부모가 0이 아니라면 도킹이 가능한 것이다.

가능한 가장 큰 번호에 도킹을 한 후, 도킹을 더 할 수 없을 때 결과를 출력하면 되는데 이를 표현하기 위한 방식으로 도킹이 된 게이트의 부모를 (그 게이트  번호-1)라고 나타내겠다.

예를 들어서

3

2

3

3

4

이러한 형태의 입력이 주어졌다고 했을 때,

첫번째로 입력된 3의 부모는 2이 된다. 

두번째로 입력된 2의 부모는 1이 된다.

세번쨰로 입력된 3의 부모는, 현재 3의 부모가 2,2의 부모가 1이기 때문에 0이 된다.

네번쨰로 입력된 3의 부모는 3의 현재 부모가 0이기 때문에 더 도킹이 되지 않는다!

따라서 여기까지 연산한 결과를 출력해주면 된다.

---

코드

 

#include<iostream>
#include<cmath>
#include<vector>
#include<queue>
#include<cstdlib>
#include<algorithm>
#include<tuple>
using namespace std;
int n, m;
int par[100001];
int counter;
int findPar(int x) {
	if (par[x] == x)return x;
	return par[x]=findPar(par[x]);
}
void merge(int x, int y) {
	if (findPar(x) == findPar(y))return;
	if (par[x] > par[y]) {
		par[x] = par[y];
	}
	else par[y] = par[x];
	
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i <= n; i++)par[i] = i;
	for (int i = 0; i < m; i++) {
		bool f = false;
		int k;
		cin >> k;
		int p = findPar(k);
		if (p != 0) {
			merge(p, p - 1);
			counter++;
		}
		else break;
	}
	cout << counter;
}

 

---

분리집합을 이미 알고있음에도, 분리집합으로 접근을 해야 한다는 사실을 인지하지 못해서 검색을 통해 해결한 문제이다.