[백준 10775] 공항

문제 링크 : 10775번: 공항 (acmicpc.net)

10775번: 공항

 

공항에 G 개의 게이트가 존재하며 1, 2, ..., G 의 번호를 가진다.

비행기는 P 개가 순서대로 도착하며 i 번째 비행기는 1 번부터 \(g_{i}\) 번까지의 게이트중 하나를

영구적으로 도킹할 수 있다고 한다.

도킹할 수 없다면 현재까지 도킹된 횟수를 출력하는 문제이다.

 

 

이 문제는 유니온 파인드 알고리즘을 활용하여 해결하였고 다음과 같이 이미지를 형상화하여 해결하였다.

예제 입력 2 에 대한 인풋을 가지고 이미지를 떠올려보자.

 

예제 입력 2 복사

4
6
2
2
3
3
4
4

 

 

 

공항의 게이트 갯수는 4, 비행기의 갯수는 6 이다.

공항을 배열 parent 로 생각한다면, parent[x] = x 으로 자기 자신을 부모로 하고 있는 셈이다.

END 같은 경우는 더 이상 docking 할 수 없도록 노드를 추가하였으며 특정 비행기가 도킹을

시도할 때, 모든 게이트에 비행기가 존재하여 END 노드로 이동하게 될 경우 종료된다.

 

① 첫 번째 비행기는 2 번 게이트에서 도킹한다.

 

 

2 번 게이트에 이동했으면 2 번 게이트는 더 이상 비행기를 받을 수 없다.

따라서, 2 번 게이트에 비행기가 올 경우 1 번 게이트로 이동시킬 수 있도록 해주었다.

즉, parent[2] = 2 에서 parent[2] = 1 이 된 셈이다. ( union(1, 2) )

 

② 두 번째 비행기는 1 번 게이트에서 도킹한다.

 

 

먼저, 1 번 비행기도 2 번 게이트에 도킹이 가능한지를 확인한다.

하지만 2 번 게이트에는 아쉽게도 어떤 비행기가 있는 상태이다.

그러나 ① 에서 2 번 게이트에서 친절하게 1 번 게이트로 이동하라는 작업을 처리를 해주었다.

따라서 1 번 비행기는 아래와 같이 1 번 게이트로 이동할 수 있게 된다.

 

 

1 번 비행기는 1 번 게이트로 이동했으므로 자연스럽게 1 번 게이트는 더 이상 비행기를 받을 수 없다.

따라서, 1 번 게이트에 비행기가 올 경우 END 로 이동시킬 수 있도록 해주었다.

즉, parent[1] = 1 에서 parent[1] = 0 이 된 셈이다. ( union(0, 1) )

 

그렇다면 나중에 어떤 비행기가 END 로 이동하게 된다면?

   => 도킹이 불가능한 상태이므로 현재까지 도킹된 비행기의 횟수를 반환하면 된다!

 

③ 세 번째 비행기는 3 번 게이트에서 도킹한다.

 

 

3 번 게이트에 이동했으면 3 번 게이트는 더 이상 비행기를 받을 수 없다.

따라서, 3 번 게이트에 비행기가 올 경우 2 번 게이트로 이동시킬 수 있도록 해주었다.

그러나 2 번 게이트로 이동하게 된다면 1 번 게이트로 이동하게 되고 결국 END 에 도달하게 된다.

즉, parent[3] = 3 에서 parent[3] = 0 이 된 셈이다. ( union(0, 3) )

 

④ 네 번째 비행기는 도킹이 불가능하다.

 

 

3번 게이트 부터 차례대로 본 결과 전부 비행기가 도킹되어 있는 상태이다.

즉, END 까지 가게 되며 도킹을 할 수 없게 된다.

 

위와 같은 플로우로 유니온 파인드로 도킹을 처리하고 부모 노드가 0 일 경우에 도킹을 중단시키고

현재까지 도킹된 횟수를 출력을 하면 된다.

 

 

풀이 코드

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <time.h>
#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

int G;
int P;
int g[100001];
int parent[100001];
int END = 0;

void input() {
	cin >> G;
	cin >> P;
	for (int i = 1; i <= P; i++)
		cin >> g[i];
}

int get_parent(int x) {
	if (x == parent[x])
		return x;
	return parent[x] = get_parent(parent[x]);
}

void go_union(int x, int y) {
	x = get_parent(x);
	y = get_parent(y);
	
	if (x > y) parent[x] = y;
	else parent[y] = x;
}

void solution() {
	int cnt = 0;
	int p;

	for (int i = 1; i <= G; i++)
		parent[i] = i;
	for (int i = 1; i <= P; i++) {
		if ((p = get_parent(g[i])) != END) {
			go_union(p - 1, p);
			cnt++;
		}
		else break;
	}

	cout << cnt;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	input();
	solution();

	return 0;
}