[Java] 백준 10775번: 공항

[문제 바로 가기] - 공항

유형 : Union-Find

이 문제도 사실 이해가 잘 되지 않아 풀이를 좀 찾아서 이해했다.

4
3
4
1
1
answer : 2

예제가 위와 같이 있을 때, 게이트의 수 G는 4, 비행기의 수 P는 3이다.
이후 주어지는 값은 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다.에 따르면 4는 1번부터 4번째 게이트 중 하나, 1은 1번 게이트에만 도킹이 가능하다.
즉, 숫자가 높을 수록 도킹할 수 있는 게이트의 선택지가 많아지는 것이다.

💡 아이디어

먼저 최대한 입력 받은 gi에 도킹해야 한다. 큰 값을 먼저 도킹해야 뒤에 작은 값이 나올 때 그 안에서 도킹할 수 있기 때문이다.

따라서 Union-Find를 사용해서 입력 받은 g의 부모와 g의 부모보다 앞에 있는 값을 union 해준다. 이때, find(g)한 값이 0일 경우 더이상 아무 곳에도 도킹하지 못한다는 뜻이므로 break 해준다.

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 백준 10775번 공항
 * - Union-Find 사용
 */

public class Main {
	public static int[] parent;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int G = Integer.parseInt(br.readLine());
		int P = Integer.parseInt(br.readLine());
		
		parent = new int[G + 1];
		for (int i = 0; i <= G; i++) {
			parent[i] = i;
		}
		
		int count = 0;
		for (int i = 0; i < P; i++) {
			int g = Integer.parseInt(br.readLine());
			
			if (find(g) == 0) break;
			
			count++;
			union(find(g) - 1, find(g));
		}
		
		System.out.println(count);
	}
	
	public static int find(int a) {
		if (parent[a] == a) return a;
		return parent[a] = find(parent[a]);
	}
	
	public static void union(int prev, int next) {
		prev = find(prev);
		next = find(next);
		
		if (prev != next) {
			parent[next] = find(prev);
		}
	}
}