(JAVA) 백준 10775번 : 공항

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

10775번: 공항

 

 

Disjoint - Set 알고리즘 중 하나.

 

 

처음에 풀긴 풀었는데

 

브루트 포스 처럼 풀어서 속도랑 메모리가 엄청났었다.

 

 

하지만

 

Disjoint-Set (Union-Find) 알고리즘으로 해결한 굇수님의 코드를 보고

 

한 대 쎄게 맞은 느낌이 들었다.

 

 

아직 나는 부족한 것이 많고, 배울 것이 많다.

 

 

 

 

처음에 하단 소스코드를 보면 무조건 헷갈리고 어려울 것이다.

 

 

핵심만 기억하자.

 

 

  -  처음 비행장 게이트 배열(parent) 에는 각각의 번호에 맞는 값이 저장되어 있다.

  **** 이 때, index는 0부터 시작한다. 1번 게이트부터 시작하지만 0번 게이트에 들어선다는 것은 즉 들어설 게이트가 없다는 뜻이므로.

 

 

  -  만약, 어떤 비행기가 1번 ~ K번까지 비행장 게이트에 도킹이 가능하다고 한다면 웬만해서는 맨 끝(K) 에 놓는 것이 후에 가장 큰 도킹 개수를 얻을 확률이 높다.

 

 

  -  그렇기 때문에, find(K) 를 통해 K번 비행장 게이트의 root 노드를 얻은 다음(이를 P라고 하자.) 

    Union(P, P - 1) 을 진행한다.

 

 

  -  이 말을 쉽게 풀어본다면

이 비행기를 K번 게이트에 넣으려고 했지만,

루트 노드가 K가 아닌 다른 노드(Q라고 하자.) 를 가리키고 있었고,

Q + 1 ~ K번 까지는 이미 비행기가 도킹되었단 소리다.

 

그래서 만약 루트 노드가 0을 가리킨다면 당장 반복문을 멈추고 결과를 리턴하면 된다.

 

 

또한, 

 

Union(P, P - 1)을 하는 이유는

 

 

"P(P는 K가 될수도, Q가 될수도 있다.) 에 이번 비행기를 도킹시킬테니 

 

만약 다음 비행기가 P로 오려고 하면 P의 루트 노드로 보내라." 

 

 

와 비슷한 의미이다.

  *** 필자는 이를 브루트 포스로 구현했었다...

 

 

 

위 핵심이 곧 이 문제의 매커니즘, 알고리즘이다.

 

 

 

 

감사합니다.

 

 

소스코드

---

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	// Disjoint-set : 공항
	// Union-find
	public class p10775 {
	public static int g, p;
	public static int[] parent;
	public static void main(String[] argc) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	g = Integer.parseInt(br.readLine());
	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 now = Integer.parseInt(br.readLine());
	int p = find(now);
	if(p != 0){
	union(p, p - 1);
	count++;
	}
	else
	break;
	}
	System.out.println(count);
	}
	public static int find(int now) {
	if(now == parent[now])
	return now;
	return parent[now] = find(parent[now]);
	}
	public static void union(int x, int y) {
	x = find(x);
	y = find(y);
	if(x != y) {
	parent[x] = y;
	}
	}
	}

view raw p10775.java hosted with ❤ by GitHub