[백준 10775] 공항 (java)

문제 보러 가기

10775번: 공항

이 문제는 유니온 파인드를 이용해 풀이할 수 있는 문제였다. 유니온 파인드를 이렇게 사용할 수 있다는 걸 알았던 문제.

 

 

 

 

 

 

 

 

 

 

문제풀이

- G개의 게이트 P개의 비행기가 주어질 때 첫 번째 비행기가 아래와 같이 2번 게이트에 도착하게 된다

-조건

1. 각 게이트당 한 개의 비행기만 도착하여 도킹할 수 있음

2. 1~gi의 게이트에 도킹이 가능 ex)  3번 게이트에 도착한다면 1,2,3번 게이트에 도킹 가능

 

- 이미 2번 게이트에 다른 비행기가 도킹된 상태에서 비행기가 또 들어오게 되면, 2 이하의 게이트 중 비어있는 게이트에 도킹해야 함

 

-여기서 유니온 파인드를 이용하여 도킹할 수 있는 즉, 비어있는 게이트를 한 번에 찾을 수 있다.

 

 

 

 

 

다시 첫 번째 비행기가 도착하는 상황으로 돌아가 아래와 같은 상황에서 살펴보면,

예시 ) G : 4 , 비행기 2->2->3->3->4->4 게이트 순으로 비행기가 들어올 때

 

 

1) 2번 게이트로 첫 번째 비행기가 도착함

- 2번 게이트에 도킹이 되면서 다음 2번 게이트로 비행기가 또 도착한다면 차선책으로 1번을 선택한다.

 

 

 

2) 2번 게이트로 두 번째 비행기가 도착함

 

- 현재 2번 게이트에는 비행기가 도킹되어있는 상태.

- 해당 게이트로 비행기가 도착하면, 차선책인 1번 게이트에 도킹

- 차선책 게이트를 0으로 설정함 => 다음에 1,2번 게이트로 도착할 시 갈 게이트가 없다

 

 

 

 

3) 3번 게이트로 세 번째 비행기가 도착함 

- 위와 같이 3번 게이트로 비행기가 도킹하면, 차선책인 2,1번 게이트가 다 도킹된 상태이므로 0번 게이트를 차선책으로 삼게 됨. -> union(3,3-1) => 2의 차선책이 0 게이트 이므로 3의 다음 차선책 게이트가 0 이 됨.

 

 

 

 

4) 3번 게이트로 세 번째 비행기가 도착함

- 위의 3번 과정으로 차선책이 0번 게이트임 => find(3) == 0

- 따라서 더 이상의 비행기가 도킹이 불가. 3개의 비행기만 도킹 가능. 답 return 

 

 

 

 

 

 

 

-> 유니온 파인드에 대한 설명

 

public class Ex_10775 {

	static int[] parent;

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		// 공항 - 분리 집합
		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 = 1; i <= G; i++) {
			parent[i] = i;
		}
		int ans = 0;
		for (int i=0;i<P;i++) {
			int g = Integer.parseInt(br.readLine());
			int emptyGate = find(g);
			if (emptyGate != 0) {//게이트에 도킹이 가능할때
				ans++;
				union(emptyGate, emptyGate - 1); //다음 차선책을 위해 union
			} else {//더이상의 차선책 게이트가 없을경우
				break;
			}
		}
		System.out.println(ans);
	}

	static int find(int x) {
		if (parent[x] == x)
			return x;
		else
			return parent[x] = find(parent[x]);
	}

	static void union(int x, int y) {
		x = find(x);
		y = find(y);

		if(x!=y)
			parent[x] = y;
	}

}