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

10775번: 공항

cpp

#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;
}

---

 

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

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

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