[BAEKJOON] 10775. 공항

Kruskal

 

문제링크

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

10775번: 공항

 

최선의 방법을 위해선 각 비행기가 도킹할 수 있는 게이트의 숫자가 최댓값이 되어야 한다.

예) plane : 5 => gate : 5    // 5번 게이터가 막혀있다면 4, 3, 2, 1 이런 식으로 게이트 할당

Kruskal 알고리즘을 활용해서 최선의 방법으로 비행기가 들어가야할 게이트를 지정해준다.

그렇게 해서 찾은 게이트 번호가 0번이라면 공항 폐쇄.

 

package acmicpc.Gold2;

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

public class 공항 {
	
	static int n, m, parent[];
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		m = Integer.parseInt(br.readLine());
		
		parent = new int[n + 1];
		
		for(int i = 1 ; i <= n ; i++) {
			parent[i] = i;
		}
		
		int ans = 0;
		for(int i = 0 ; i < m ; i++) {
			
			int p = Integer.parseInt(br.readLine());
			int pSet = findSet(p);
			
			if(pSet == 0) break;
			
			ans++;
			union(pSet, pSet - 1);
		}
		
		System.out.println(ans);
	}
	
	public static int findSet(int x) {
		if(x == parent[x]) return x;
		
		return parent[x] = findSet(parent[x]);
	}
	
	public static void union(int a, int b) {
		
		int aSet = findSet(a);
		int bSet = findSet(b);
		
		if(aSet == bSet) return;
		
		parent[aSet] = bSet;
		
	}
}

Kruskal 알고리즘을 이런식으로도 사용할 수 있다는 것에 감탄했다....