백준 10775 공항

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

문제만 보면 솔직히 무슨소리인지 잘 모르겠다.

예제와 함께 이해해보자.

첫 줄에 게이트의 개수가 주어진다.
두 번째 줄에 비행기의 개수가 주어진다.
이후 비행기의 개수만큼 gi 값이 주어지는데, 해당 비행기는 1~gi까지의 게이트에 도킹할 수 있다.

그럼 예제 1번을 분석해보자.

게이트가 1 2 3 4가 있으며 1~4에 도킹 가능한 비행기, 1에 도킹가능한 비행기, 1에 도킹가능한 비행기가 순서대로 도착한다.

그럼 1~4에 도킹 가능한 비행기는 4에 도킹하고, 1에 도킹가능한 비행기는 1에 도킹한다.

맨 마지막으로 오는 1에 도킹가능한 비행기는 자리가 없으므로, 종료하고 최대 2대가 도킹 가능하다.

예제 2번을 분석해보자.

게이트가 1 2 3 4가 있으며, [1~2, 1~2, 1~3, 1~3, 1~4, 1~4] 비행기가 도착한다.

처음 1~2 비행기는 2에 도킹하고, 두 번째 1~2 비행기는 1에 도킹한다.
그리고 세 번째 도착하는 1~3 비행기는 3에 도킹한다.

다음 네 번째 1~3 비행기는 더 이상 도킹할 공간이 없으므로, 남은 비행기들은 도착하지 못하고 종료된다. 따라서 최대 3대 도킹 가능하다.

느낌이 대충 올 것이다. 가능한 한 숫자가 큰 게이트쪽을 먼저 채워야한다고.

위를 토대로 풀이방법을 간단하게 구성해보자.

1. 게이트의 사용 여부를 표시할 Boolean 배열을 구성한다.
2. 각 비행기들마다 가능한 한 높은 숫자의 게이트를 채운다
   (4라면, 4번 게이트 사용 가능하면 바로 넣고, 4번 찼으면 3번 보고 넣는 식)
3. 만약 다음 비행기가 더 이상 도킹할 게이트가 없다면 종료하고, 사용중인 게이트의 개수를 센다.

간단하게 보면 위와 같다.

하지만 게이트의 개수와 비행기의 개수는 최대 100,000이다.

풀이방법 2번을 생각해보면, 높은 숫자의 gi를 가진 비행기가 도착했는데 해당 gi값의 게이트가 사용중이면, 해당 gi값보다 낮은 게이트 중 최댓값의 게이트에 넣어야 한다.

이 과정을 리니어하게 진행하면 $O(n^2)$에 가까워져 시간초과가 날수 있다 판단하였다.

따라서 풀이방법 2번을 개선할 필요가 있다.

나는 Union Find 알고리즘을 풀이의 열쇠로 느꼈다.

gi값이 4인 비행기가 도착했는데, 3번과 4번이 이미 차있다면?

1	2	3	4
1	2	2	2

Union Find 배열을 위처럼 구성하여 2번에 들어가도록 하는 것이다.

즉 Union Find를 통해 현재 gi 이하의 빈 게이트들 중 가장 큰 게이트를 가리켜 바로 도킹하도록 하는 방법이다.

예제 2번을 따라가보며 Union Find배열이 어떻게 변화하는 지 보자.

게이트 4개, 비행기 6대 [2, 2, 3, 3, 4, 4]이다.

1	2	3	4
1	2	3	4

처음엔 각 게이트들은 자기 게이트가 비었으므로 자기 자신의 숫자를 가진다.

먼저 gi가 2인 비행기가 도착한다.

2번 게이트는 비었으므로 2번 게이트에 넣는다.

게이트에 넣으며 find(gi) - 1과 find(gi)를 union한다. (여기선 1과 2)

1	2	3	4
1	1	3	4

다음으로 gi가 2인 비행기가 도착한다.

2번 게이트는 이미 도킹했고, 2번 게이트는 다음 빈 게이트는 1이라고 가리키므로, 1번 게이트에 넣는다.

게이트에 넣으며 find(gi) - 1과 find(gi)를 union한다 (여기선 0과 1)

1	2	3	4
0	0	3	4

1번과 2번 게이트가 0을 가리키게 되었다. 현재 상황에서 gi가 2 이하인 비행기가 오면 망한다는 얘기이다.

하지만 다음으로 gi가 3인 비행기가 도착한다.

3번 게이트는 비었으므로 3번 게이트에 넣고, 3번과 2번을 union한다.

1	2	3	4
0	0	0	4

3번과 2번을 union하면 원래 3번 인덱스가 2로 바뀌지만, find를 호출할 때마다 경로단축이 되어 결국 위처럼 바뀐다.

다음으로 gi가 3인 비행기가 도착한다.

find(gi)가 0이므로, 해당 비행기는 갈 곳이 없다. 따라서 3개의 게이트에 도킹하고 종료된다.

lateinit var gates: IntArray

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val G = readLine().toInt()
    val P = readLine().toInt()

    val gi = IntArray(P){readLine().toInt()}
    gates = IntArray(G + 1){ it }

    val docking = BooleanArray(G + 1){false}
    var answer = 0
    for(g in gi){
        if(find(g) == 0) break
        docking[find(g)] = true
        union(find(g) - 1, find(g))
    }

    docking.forEach { if(it) answer++ }
    print(answer)
}

fun find(x: Int): Int{
    if(gates[x] == x) return x
    gates[x] = find(gates[x])
    return gates[x]
}

fun union(x: Int, y: Int){
    gates[find(y)] = find(x)
}

처음 풀이할때 성공해버려서 몰랐는데, 글을 쓰며 다시 보니 사용 여부를 체크하는 docking 배열(BooleanArray)는 필요하지 않은 것 같다.

그냥 union find에 사용된 배열 요소 중 인덱스와 값이 다르면 해당 게이트는 사용중이라고 봐도 될 것 같다.