[백준/JAVA] 10775_공항

백준🔗

10775번: 공항

 

 

문제

 

 

간단 풀이

각각의 비행기는 자신보다 번호가 작거나 같은 게이트 중에서 비어있는 곳 중 가장 큰 번호로 도킹하면 된다. 번호가 n인 비행기라면 순서대로 n번, (n-1)번 게이트, (n-2)번 게이트... 가 우선순위를 가지는 것이다. 즉, 그리디 문제이다! 

처음에는 단순히 G+1 크기의 int형 게이트 배열을 만들어서 비행기가 도킹된 게이트는 1, 도킹되지 않은 게이트는 0으로 두어 비행기보다 작거나 같은 번호 중 0인 곳에 비행기를 도킹하도록 코드를 구현했다. 그러나 71%에서 시간 초과가 났다 (그럼 그렇지 골드2가 이렇게 간단히 풀릴 리가 없었다...) 아무래도 0인 곳을 찾을때까지 반복적으로 탐색을 하면서 시간초과가 발생한 듯하다.

 

 

탐색 과정을 어떻게 줄일 수 있을지 고민하다가 검색을 해보니.. 유니온 파인드 자료구조를 사용해야 했다. 

예전에 서로소 집합을 배우면서 정리했던 내용을 끄집어 내서 다시 살펴보니..

 

 

find set(x) : x를 포함하는 집합을 찾는 연산

union(x, y) : 합집합. x집합에 y집합을 포함시키는 것

=> Union-Find : 대표적인 그래프 알고리즘으로, 두 노드가 같은 집합에 속하는지 판별하는 알고리즘

 

 

이 문제에서는 int형 게이트 배열에 해당 번호의 비행기가 들어왔을 때

도킹될 수 있는 번호를 저장한다.

아직 도킹되기 전의 게이트는 해당 게이트의 번호가 저장되어 있을 것이고,

이미 도킹된 게이트에는 다른 남은 게이트들 중 가장 높은 우선순위를 가지는

게이트의 번호가 저장되어 있을 것이다.

비행기가 들어왔을 때 findSet을 이용해 도킹 가능한 게이트에 도킹 후

게이트 배열 정보를 업데이트 하는 과정을 반복하다가,

비행기가 도킹을 하려는 게이트가 도킹 가능한 번호로 0을 가지고 있다면

더 이상 도킹이 불가능하기 때문에 그 때까지 카운트한 비행기 대수를 출력하면 된다. 

유니온 파인드를 사용하면 특정 번호의 비행기가 들어왔을 때 몇 번 게이트로 갈 지

일일이 탐색하지 않고 바로 알 수 있기 때문에 시간초과를 해결할 수 있었다.

 

 

유니온 파인드에서 연산 효율을 높이기 위한 방법으로 rank, path compression이 있는데 해당 내용에 대해서도 추후에 복습이 필요할 것 같다.

 

 

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	static int[] gates;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int G = Integer.parseInt(br.readLine()); // 게이트 수
		int P = Integer.parseInt(br.readLine()); // 비행기 수
		gates = new int[G + 1];
		for (int i = 1; i <= G; i++) {
			gates[i] = i; // 해당 번호의 비행기가 들어왔을 때, 들어갈 수 있는 게이트 중 가장 큰 값 (0이면 불가능)
		}
		int cnt = 0;
		for (int i = 0; i < P; i++) {
			int airplane = Integer.parseInt(br.readLine());
			int target = findSet(airplane);
			if (target == 0)
				break;
			union(target - 1, target);
			cnt++;
		}
		bw.write(String.valueOf(cnt));
		bw.flush();
		br.close();
		bw.close();
	}

	// x를 포함하는 집합의 대표자 반환
	static int findSet(int x) {
		if (gates[x] == x)
			return x;
		return gates[x] = findSet(gates[x]);
	}

	// x집합에 y집합 포함시키기
	static void union(int x, int y) {
		gates[findSet(y)] = findSet(x);
	}
}

 

참고 자료

[BOJ] 백준 10775번 : 공항 (JAVA)

 

[알고리즘] 유니온 파인드 (Union-Find)