[PS] 백준 10775 : 공항

문제

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

10775번: 공항

해설

 

처음 이 문제를 접했을 때 왜 Union-Find 문제인지 깨닫고 접근하기 까지 오랜 시간이 걸렸습니다.

 

일반적으로 Kruskal 알고리즘을 통해 Union-Find 자료구조를 접하셨을 것 입니다. 하지만 Kruskal 알고리즘에서 사용하는 Union-Find 구조의 부모를 갱신하는 방법과는 조금 다른 방식인 문제에서 요구하는 방식대로 Union을 구성해야 합니다. 

 

이 문제에서는 도킹을 하고싶은 게이트가 입력으로 주어졌을 때 이를 도킹할 수 있는지 여부를 따져봐야 합니다. 이를 어떻게 하면 Union-Find 구조로 해석할 수 있는지가 이 문제의 해결의 관건이라고 할 수 있습니다. 

 

i번째 비행기는 1부터 gi까지의 게이트 중 한 곳에 도킹할 수 있으므로 역순으로 gi번 부터 1번까지 자리가 있는지 시도해 보는것이 이 문제를 해결하는 기본 아이디어 입니다. 이렇게 할 경우 비행기는 가능한 경우 항상 높은 번호를 가지고 있는 게이트 부터 도킹될 것 입니다. 

 

g번 게이트 부터 자리가 차 있는지 없는지 매번 탐색을 수행하게 된다면 제한 시간 내에 문제를 해결 할 수 없습니다. 이 때 Union-Find 구조를 활용하여 도킹이 성공한 게이트의 부모를 이전 게이트를 가리키게 한다면 탐색을 최적화 할 수 있습니다.  

 

총 게이트의 개수가 4이고 입력으로 3이 연속해서 3번 들어오는 경우를 고려해보겠습니다.

 

1. 가장 처음 비행기는 게이트가 비어 있으므로 3번 게이트에 도킹에 성공할 것이고 3번 게이트는 이전 게이트인 2번 게이트를 가리킬 것입니다. 

 

2. 두번째 비행기는 3번 게이트에 도킹하려고 하였지만 3번 게이트가 2번게이트를 가리키고 있고 2번 게이트가 비어 있으므로 2번 게이트에 도킹을 하고 Find 최적구조를 활용하여 2번 게이트와 3번 게이트 모두 1번 게이트를 가리키게 될 것입니다. 

 

3. 마지막 비행기는 3번 게이트에 도킹하려고 하였지만 비어있는 1번 게이트를 가리키고 있으므로 1번 게이트에 도킹을 하게 될 것입니다. 

 

위 처럼 parent[gate] = gate - 1 로 갱신을 이어나가면서 Union-Find로 문제를 해결 할 수 있습니다.

 

코드

 

Union-Find

public class BOJ_10775_공항 {
	static StringBuilder sb = new StringBuilder();
	static int g, p;
	static int[] group;
	static int find(int u) {
		if(group[u] < 0) return u;
		return group[u] = find(group[u]);
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		g = Integer.parseInt(br.readLine());
		p = Integer.parseInt(br.readLine());
		group = new int[g+1];
		Arrays.fill(group, -1);
		int result = 0;
		for(int i = 0; i<p; i++) {
			int d = Integer.parseInt(br.readLine());
			// 해당 게이트에 도킹할 수 있는지 여부를 체크한다.
			int dock = find(d);
			// 도킹이 불가능하면 종료
			if(dock == 0) break;
			// 도킹할 수 있으면 해당 게이트의 도킹 가능한 개수를 1줄인다. 
			// 이렇게 되면 다음번에 기존에 도킹한 곳을 찾으려면 
			// dock - 1 번째를 찾을 것이고 이 때 group[dock] 은 
			// 해당 게이트 까지의 도킹가능한 대수를 의미한다.
			group[dock] = dock - 1;
			result++;
		}
		System.out.println(result);
	}
}

Union-Find (HashMap)

/** 
* 알고리즘 : Union-Find Using HashMap
* 1. 일반 Kruskal 알고리즘을 구현할 때와 다르게 Find 후 Union을 재정의 해야 한다.
* 2. Find에서 자신이 속한 그룹 즉 값이 들어갈 공간을 찾는 것은 같지만 
* 3. Union에서의 부모를 갱신하는 부분이 일반적인 Union-Find와 다르다.
* 4. 이동방향과 문제의 요구에 따라 Union에서 부모를 재정의 하는 부분이 달라져야 한다. 
* 5. 이 문제에서의 경우 find 함수에서의 else 부분이 Union 부분의 동작을 수행한다.
* 6. find를 재귀적으로 수행하면서 빈 공간을 찾고 빈 공간을 찾으면 그 부모를 반환
*/
public class BOJ_10775_공항 {
	static StringBuilder sb = new StringBuilder();
	static int g, p;
	static Map<Integer, Integer> map = new HashMap<>();
	
	static int find(int n) {
		if(!map.containsKey(n)) {
			map.put(n, n - 1);
			return n - 1;
		} else {
			int temp = find(map.get(n));
			map.put(n, temp);
			return temp;
		}
	}
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		g = Integer.parseInt(br.readLine());
		p = Integer.parseInt(br.readLine());
		int result = 0;
		for(int i = 0; i<p; i++) {
			int n = Integer.parseInt(br.readLine());
			
			int dock = find(n);
			if(dock < 0) break;
			result += 1;
		}
		System.out.println(result);
	}
}