[백준] 10775 공항 - 유니온파인드(Union Find) + 그리디(greedy) JAVA

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

10775번: 공항

코드설명

유니온 파인드 문제입니다.

 

문제로직입니다.

 

1. parent[] 는 게이트의 집합을 의미하도록 합니다.
2. 기본 조건은, 만약 게이트가 모두 찼을경우에는 0 이라는 분리집합에 속하도록 합니다.
3. 그리디하게 본인이 원하는 게이트가 비어있다면 바로 해당 게이트를 채워줍니다. 그리고서 해당 게이트는 이미 도킹되었으므로 본인보다 한단계 작은 게이트와 unionParent, 분리집합을 합쳐줍니다.
4. 문제예시와 함께 살펴보겠습니다.
5. 만약 1번 비행기가 2번 게이트에 도킹하려고 합니다.
   1. 1번 비행기는 2번 게이트의 집합이 0인지 아닌지 확인합니다. 만약 0 이라면, 2번 게이트와 1번 게이트 모두 이미 도킹된 상태인것입니다.
   2. 1번 비행기가 2번게이트에 처음으로 도킹하였으므로 emptyGate = 2 로 찾게되고 후에 answer += 1 처리를 통해 비행기가 도킹한것의 개수를 세어줍니다. 도킹처리하기 위해 1번 게이트와 2번 게이트를 unionParent(2, 1) 를 해줍니다. 이렇게 될경우 parent[1] = 1, parent[2] = 1 으로 변하게 됩니다.
6. 만약 2번 비행기가 2번 게이트에 도킹하려고 합니다.
   1. 2번 비행기는 2번 게이트의 집합을 확인합니다. 아까 1으로 변한것을 확인했으므로, emptyGate = 1 로 설정한 후에 answer += 1 처리를 통해 도킹되었다는 표시를 합니다. 
   2. union(0, 1) 을 시도하게 되고, parent[0] = 0, parent[1] = 0 이 됩니다. 이후에 findParent(2) 를 하더라도 parent[2] 는 parent[1] 을 가리키고 있으므로 0 으로 바뀌게 될 것이므로 parent[2]는 따로 0 으로 바꿔주지 않습니다.

 

위의 로직을 통하여 해결할 수 있습니다.

 

코드

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

public class Main {
	
	public static int G, P;
	public static int answer = 0;
	public static int[] parent;
	public static int findParent(int x) {
		if(x == parent[x]) return x;
		return parent[x] = findParent(parent[x]);
	}
	
	public static void unionParent(int a, int b) {
		a = findParent(a);
		b = findParent(b);
		if( a < b ) {
			parent[b] = a;
		}else {
			parent[a] = b;
		}
	}
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	G = Integer.parseInt(st.nextToken());
    	st = new StringTokenizer(br.readLine());
    	P = Integer.parseInt(st.nextToken());
    	
    	parent = new int[G+1];
    	for(int i=0;i<G+1;i++) {
    		parent[i] = i;
    	}
    	
    	for(int i=0;i<P;i++) {
    		st = new StringTokenizer(br.readLine());
    		int g = Integer.parseInt(st.nextToken());
    		int findGate = findParent(g); //findParent를 통해 속해있는 집합의 Index를 알아냅니다.
    		if(findGate == 0) { //만약 속해있는 집합이 0 이라면, 불가능한 경우입니다.
    			break;
    		}
    		answer += 1;
    		unionParent(findGate, findGate-1); //gate를 사용할때마다 상위의 게이트로 분리집합을 UnionParent합니다.
    	}
    	System.out.println(answer);
    	
    }
    
    
}