BOJ-10775 공항 Swift

문제

오늘은 신승원의 생일이다.

박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.

공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.

공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.

신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

입력

첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 105)가 주어진다.

두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 105)가 주어진다.

이후 P개의 줄에 gi (1 ≤ gi ≤ G) 가 주어진다.

출력

승원이가 도킹시킬 수 있는 최대의 비행기 수를 출력한다.

내가 푼 풀이

- 게이트에 최대로 도킹할 수 있는 비행기의 수를 구한다.

- P개의 줄에 숫자 N이 주어지면, 해당 비행기는 1부터 N까지의 게이트에 도킹할 수 있다.

- 이를 생각해보면 1은 1부터 1까지 1개, 5는 1부터 5까지 5개의 게이트 중 하나를 도킹할 수 있다는 의미다.

- 최대한 많은 비행기를 도킹시키려면 주어진 값의 최댓값부터 도킹을 해야 비행기를 최대로 도킹할 수 있다.

- 이를 위해 숫자 N이 주어지면 N부터 1까지 도킹되어 있지않으면 도킹하는 방법을 이용했지만 , 시간초과가 떴다.

- 이 문제는 Union-Find 알고리즘을 이용해서 풀어야한다.

 

Union-find를 이용하며 예제를 풀어본다.

게이트 수 G = 4, 비행기 수 P = 6, 도착하는 비행기 배열 [2, 2, 3, 3, 4, 4]

게이트를 배열로 표현한다.

처음에 각 게이트들은 자신의 게이트가 비어있으므로, 자신의 게이트를 가리킨다.

0	1	2	3	4
0	1	2	3	4

먼저 Gi가 2인 비행기가 도착하면, 해당 비행기는 1부터 2까지 최댓값인 곳에 도킹한다.

게이트 2가 현재 비어있으므로, 게이트 2에 도킹한다.

게이트 2에 도킹을 한다면, 게이트 2는 도킹할 수 없으므로 게이트 1을 가리킨다.

이는 Union-find에서 find(2)-1 , find(2)를 union 하는 것이다.

0	1	2	3	4
0	1	1	3	4

다음에 Gi가 2인 비행기가 도착한다.

2번 게이트에 도킹하려 했지만, 이미 2번게이트에 도킹이 되어있다.

2번 게이트는 1번을 가리키므로, 1번 게이트에 도킹을 한다.

이때 find(1) - 1과 find(1)을 union 한다. (0, 1)

0	1	2	3	4
0	0	0	3	4

위 배열로 보았을 때, Gi가 2나 1인 비행기가 오면 더 이상 도킹할 수 없는 상황이다.

다음 비행기의 Gi는 3이다.

3번 게이트에 도킹을 하고, 2번과 union을 해준다.

0	1	2	3	4
0	0	0	0	4

그다음 비행기의 Gi값이 3이지만, 3번 게이트부터 1번 게이트까지 모두 자리가 없으므로, 종료한다.

 

이 문제는 이해하기 쉽지만, 결국 Union-find 알고리즘을 알고 있는지 물어보는 문제인듯하다..

 

위 알고리즘을 통해 코드로 구현해 보자.

 

import Foundation

var g = Int(readLine()!)!
var p = Int(readLine()!)!
var arr = Array(1...g)
arr.insert(0, at: 0)
var result = 0

// Union-find 의 find
func find(_ x: Int) -> Int {
    if arr[x] == x { return x}
    arr[x] = find(arr[x])
    return arr[x]
}
// Union-find 의 union
func union(x: Int, y: Int) {
    arr[find(y)] = find(x)
}

for i in 0..<p {
    var num = Int(readLine()!)!
    // 해당 비행기가 도킹할 수 있는지?
    // 도킹했다면 union을 통해 배열 최신화
    if find(num) == 0 { break }
    result += 1
    union(x: find(num) - 1, y: find(num))
}
print(result)