[백준 C++] 10775 공항 - 분리집합

10775번: 공항

#include <iostream>
using namespace std;

bool LandingGate[100001];
int Root[100001];

int Find(int Node)
{
	if (Node == Root[Node])
	{
		return Node;
	}

	return Root[Node] = Find(Root[Node]);
}

void Union(int NodeA, int NodeB)
{
	int A = Find(NodeA);
	int B = Find(NodeB);
	int Min = min(A, B);
	Root[A] = Min;
	Root[B] = Min;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	for (int i = 1; i <= 100000; ++i)
	{
		Root[i] = i;
	}

	int G, P;
	cin >> G >> P;

	int Cnt = 0;
	for (int i = 1; i <= P; ++i)
	{
		int g;
		cin >> g;
		if ((g = Find(g)) == 0)
		{
			break;
		}

		Union(g, g - 1);
		++Cnt;
	}

	cout << Cnt;
}

---

 

유니온 & 파인드 연산을 이용해서 도킹된 게이트끼리 묶어주면서 푸는 문제입니다.

입력 받은 게이트 번호의 파인드 연산이 맨앞 번호가 아닐 동안,

해당 게이트와 바로 앞 게이트를 유니온 연산하고 도킹 개수를 카운팅하는 작업을 반복해줍니다.