[백준] 10775번 - 공항

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

문제

오늘은 신승원의 생일이다.

박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.

공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.

공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 $g_i$ (1 ≤ $g_i$ ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.

신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

입력

첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 105)가 주어진다.

두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 105)가 주어진다.

이후 P개의 줄에 $g_i$ (1 ≤ $g_i$ ≤ G) 가 주어진다.

출력

승원이가 도킹시킬 수 있는 최대의 비행기 수를 출력한다.

---

제출 코드

• Union-Find 사용

• 각 비행기는 자신이 도킹할 수 있는 최대 게이트 번호를 입력받는다.

• 이 게이트 번호를 findSet(g) 함수를 통해 확인하여, 실제 도킹할 수 있는 게이트(비어있는 가장 큰 번호)를 찾는다.
  
  

• 예제1의 경우

1. 제일 첫번째 비행기가 findGate(g)를 사용해 도킹할 수 있는 가장 높은 게이트에 도킹한다.
2. 다음 비행기가 그보다 작은 번호의 게이트에 도킹해야 하기 때문에, findGate와 findGate - 1을 연결한다.
3. 마지막 3번째 비행기의 경우 2번째 비행기에서 1번 게이트에 도킹한 후 0과 연결했으므로, 1번 게이트로 갔을 때 부모가 0이 출력된다.
4. 따라서, findGate가 0이므로 도킹 불가능하다.

package algo.practice;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class M_10775_공항_union_find {

	static int G, P;

	public static void main(String[] args) throws Exception {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		G = Integer.parseInt(in.readLine());
		P = Integer.parseInt(in.readLine());

		parents = new int[G + 1];

		makeSet(); // 각 게이트 초기화

		int ans = 0; // 도킹 가능한 비행기의 수를 셈

		for (int i = 0; i < P; i++) {
			int g = Integer.parseInt(in.readLine());
			int findGate = findSet(g); // 비행기가 도킹 가능한 가장 큰 게이트 찾기

			if (findGate == 0) { // 0이면 도킹 불가
				break;
			}

			ans++; // 도킹 성공한 비행기의 수 증가
			union(findGate, findGate - 1); // 현재 도킹한 게이트와 그보다 작은 게이트를 연결
		}

		System.out.println(ans);

	}

	static int[] parents;

	static boolean union(int from, int to) {

		from = findSet(from);
		to = findSet(to);

		if (from == to) {
			return false;
		}

		// 작은 쪽을 부모로 설정해 두 집합을 합침
		if (parents[from] > parents[to]) {
			parents[from] = to;
		} else {
			parents[to] = from;
		}

		return true;
	}

	static int findSet(int v) {

		if (parents[v] == v) {
			return v;
		} else {
			return parents[v] = findSet(parents[v]);
		}
	}

	static void makeSet() {

		for (int i = 1; i <= G; i++) {
			parents[i] = i;
		}
	}

}