[BOJ - JAVA] 10775 - 공항 (Union-Find, 그리디)

# 주소

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

10775번: 공항

# 문제

# 문제 해설 및 코드 리뷰

import java.util.*;
class Main{
	static int[] parents;
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int g = scan.nextInt();
		int p = scan.nextInt();
		parents = new int[g + 1];
		//부모 노드는 최초에 방문시 i번 비행기가 방문하므로 i삽입
		for(int i = 0; i <= g; i++)
			parents[i] = i;
		int count = 0;
		while(p-- > 0) {
			int x = scan.nextInt();
			//x가 주어질 때 x의 부모를 temp에 저장
			int temp = find(x);
			if(temp != 0) {
				count++;
				union(temp - 1, temp);
				//i번 비행기는 i번 이하의 공항에 잘 착륙되었으므로 이보다 낮은 수를 미리 parents에 삽입
			}else break;
		}
		System.out.println(count);
	}
	static void union(int a, int b) {
		int pa = find(a);
		int pb = find(b);
		if(pa != pb)
			parents[pb] = pa;
		//a의 부모, b의 부모를 구하여 분리된집합일 경우 pa 주입
	}
	static int find(int x) {
		if(parents[x] == x) return x;
		return parents[x] = find(parents[x]);
		//x번 방문이 최초면 x return하고 아니면 parents[x]의 부모를 구함
	}
}

문제가 이해가 안되어서 질문게시판에서 글들을 쭉 보고나서야 이해할 수 있었던 문제였습니다.

문제를 요약하자면 

1. G개의 게이트가 주어지고 P개의 비행기가 입항하는데, 비행기는 주어진 입력번호 이하의 공항에만 착륙할 수 있습니다.

2. 예를 들어 5번의 비행기가 착륙하려 한다면, 5번 공항에는 어떠한 다른 비행기도 착륙되어있어선 안되고 만약 착륙되어 있다면 5번보다 작은 4번 공항에 착륙했는지의 여부를 탐색해야 합니다.

3. 따라서 최악의 경우엔, 10만 x 10만의 시간 복잡도가 발생하여 시간 초과가 발생할 수 있습니다. 이를 해결하기 위해 Union-Find를 사용합니다.

Union-Find 알고리즘이 무엇인지 먼저 살펴보겠습니다. 제 블로그에선 처음 다루는 것 같은데 아직 10문제 정도밖에 안 풀어본 거라 설명하기 애매했던 찰나 그리디랑 맞물려서 출제가 되어 좋은 문제라 생각들어 포스팅하게 되었답니다.

https://kistone.tistory.com/58

[JAVA] Union-Find

Union-Find를 이해하기 위해 다음 포스팅을 읽고 와주시길 바랍니다.

Union-Find를 사용하는 결정적인 이유는 합집합을 찾기 위함이며 이는 다른 말로, 분리 집합을 구별해 내어 중복된 집합일 만들어질 경우 (부모 노드가 같을 경우) 더 이상 탐색을 종료할 수 있습니다.

이 문제의 해설 코드와 Union-Find의 구조가 거의 같으므로 문제 코드를  보며 해석해 봅시다.

Scanner scan = new Scanner(System.in);
		int g = scan.nextInt();
		int p = scan.nextInt();
		parents = new int[g + 1];
		//부모 노드는 최초에 방문시 i번 비행기가 방문하므로 i삽입
		for(int i = 0; i <= g; i++)
			parents[i] = i;
		int count = 0;

입력은 다음과 같습니다.

부모 Union-Find문제의 특징은 최초의 parents에는 i를 삽입하는 경우가 많습니다.

왜냐하면 노드 결합을 하기 전인 아무 것도 시행하지 않은 상태에서의 i번 노드의 부모는 i번 노드인 자기 자신이기 때문입니다.

이는 값 초기화와 같습니다.

while(p-- > 0) {
			int x = scan.nextInt();
			//x가 주어질 때 x의 부모를 temp에 저장
			int temp = find(x);
			if(temp != 0) {
				count++;
				union(temp - 1, temp);
				//i번 비행기는 i번 이하의 공항에 잘 착륙되었으므로 이보다 낮은 수를 미리 parents에 삽입
			}else break;
		}

x가 입력이 될 때 x의 부모를 구해야 하는데요.

최초의 시행일 경우 x번의 부모는 당연히 x번이 되므로 temp에는 자기 자신의 값인 x가 삽입됩니다.

하지만 여기서 예외가 발생할 수 있는데요.

만약 temp가 0이 되었을 경우, x의 부모가 0이란 것이고 이는 다른 어떤 노드가 이미 1번 노드를 사용하여 0번 노드를 남겨두었단 것을 의미하는데요.

이게 무슨 말이냐면, 저희는 find 함수를 이용하여 부모 노드를 구할 수 있습니다.

find의 내부를 살펴보면

static int find(int x) {
		if(parents[x] == x) return x;
		return parents[x] = find(parents[x]);
		//x번 방문이 최초면 x return하고 아니면 parents[x]의 부모를 구함
	}

다음과 같습니다. 

parents의 x번 노드가 x면 x를 return하고(최초의 시행) 그렇지 않을 경우엔 parents[x]는 parents[x]의 부모를 재귀를 이용하여 구하는데요.

이처럼  2번째 줄의 if문이 아니라 그 아랫줄의 parents[x]의 부모를 구하는 이유는 parents[x]가 x가 아니기 때문입니다.

그 이유가 바로 union함수 때문이라고 말씀 드릴 수 있겠는데요.

union함수는

static void union(int a, int b) {
		int pa = find(a);
		int pb = find(b);
		if(pa != pb)
			parents[pb] = pa;
		//a의 부모, b의 부모를 구하여 분리된집합일 경우 pa 주입
	}

다음과 같이 생겼습니다.

a라는 값과 b라는 값을 하나의 집합으로 만들겠다 라고 생각하시면 좋을 것 같습니다.

여기서 a는 b보다 1 작은 값이 될텐데요. 

그 이유는 그리디적으로 생각을 했을 때, 10000번 비행기가 방문한다면 모든 입력값은 다 다르기 때문에 10000번 비행기가 최초로 들어왔다면 10000번 게이트에는 10000번 비행기를 넣으시면 됩니다.

그런데 그 다음에 또 10000번 비행기가 방문한다면 어떻게 할까요? 9999번 게이트를 이용하는 것이 좋겠죠?

만약 이것도 이해가 안되신다면 하나의 예시를 설명드리겠습니다.

 

10000원을 가지고 있는데 9150원짜리 물건을 사고 850원을 거슬러 받는다고 합시다.

근데 여러분은 동전이 딸그닥 거리는게 싫어서 최소한의 동전을 갖고 싶은거에요. 그럼 어떤 동전을 받는 것이 최선일까요?

500원짜리 한개 + 100원짜리 3개 + 50원짜리 한 개 겠지요?

 

공항 문제도 마찬가지입니다.

입력 값이 어떤 것이 주어지든, 일단 주어진 비행기를 주어진 공항 번호에 주입 시켜보고, 안되면 1씩 감소시켜 나가면서 들어갈 때 까지 순회하는 것입니다. 그런데 이를 일일이 다 순회하게 되면 최악의 경우에 시간초과가 발생할 수 있기 때문에 이를 방지하고자 Union-Find를 사용하는 것이지요.

 

자 다시 본론으로 돌아가서, union함수를 다시 보시면 

static void union(int a, int b) {
		int pa = find(a);
		int pb = find(b);
		if(pa != pb)
			parents[pb] = pa;
		//a의 부모, b의 부모를 구하여 분리된집합일 경우 pa 주입
	}

a라는 값은 b보다 1이 작은 값이라고 말씀드렸습니다.

이유는, 이미 b번 공항은 b라는 비행기가 착륙했기 때문에 저희가 해야할 건, 또 b번 비행기가 들어올려고 할 때 b가 아니라 b - 1번으로 들어오라고 명령해야 하는 것입니다.

그러므로 b의 게이트에 a의 비행기가 들어가야 하는 것이랍니다.

b의 게이트의 부모는 pb, a의 게이트의 부모는 pa라고 했을 때 만약 같은 부모가 아니라면 parents[pb]에 pa를 삽입합니다.

이걸 굳이 안해줘도 정답에 지장은 없으나, Union-Find는 이 제어문이 꼭 필수입니다. 같은 부모일 때에는 parents의 값이 변경되면 안되기 때문입니다. if문이 없어도 정답이 되는건 문제 특성상 같은 부모가 되는 경우가 없어서 그런 것 같습니다.

아마 같은 부모가 되는 경우는 위에서 temp가 0이 될 때 이미 분기를 시켰기 때문이라 생각합니다.

또, pb도 굳이 안구해도 정답에는 전혀 지장 없습니다. 이는 문제 특성상 예제로 주어지는 값으로 10000게이트와 1000게이트가 서로 같다는 그러한 설명이나 묘사가 없기 때문으로, 문제 특성상 그런 것이지 Union-Find 알고리즘을 사용할 때에는 노드간의 서로 부모노드를 확인하여 값을 주입시켜 주어야 한다는 것을 꼭 기억하셨음 좋겠습니다. (저에게 하는 말입니다.)

최초에 10000이 들어왔다면 b는 10000, a는 9999이므로 parents[10000] = 10000가 될 것입니다.

그런데 또 10000이 들어왔다면 find함수에서 parents[x] = find(parents[10000])이므로 parents[10000] = 9999가 됩니다.

그렇게 10000이 들어올 때마다 9999에서 값이 또 점진적으로 감소하게 된답니다.

이처럼 parents의 값을 다음에 이용할 비행기가 이용하기 좋게 아무도 이용하지 않은 게이트 값으로 오게끔 유도하는 함수를 union이라고 생각할 수 있으며 find를 통해 최초의 방문인지 여부를 판단하고 아니라면 부모의 값을 불러오는 함수라고 생각할 수 있습니다.

그리고 부모의 노드가 0이 나온다면 (temp가 0이라면) 이미 누군가가 1번 부모 공항값을 썼다는 것이고 이제는 더 이상 1번 노드를 쓸 수 없기 때문에 앞의 노드에서 1번 -> 0번으로 바꾸어놨기 때문에 temp가 0이 나오는 것이며 이 때에는 break하여 while문을 빠져나오면 되겠습니다.

감사합니다.