[Kotlin][Alogrithm] 9376 - 탈옥

D.O·2024년 2월 10일

문제 요약

문제에서 주어진 감옥은 1층짜리 건물로, 평면도에는 벽(*), 문(#), 빈 공간(.), 죄수의 위치($)가 표시되어 있습니다.
감옥은 무인 감옥이며, 두 명의 죄수만이 그곳에 있고 최소한의 문을 통과해서 두 죄수를 탈옥 시키는 것이 목표입니다.

문제 접근

감옥 확장

문제를 잘 생각해보면 최소의 문을 열어 두명의 죄수가 탈옥하는 경우는 두 가지 경우로 나눠 볼 수 있습니다.

두명의 죄수가 같은 출구로 나가는 경우
두명의 죄수가 다른 출구로 나가는 경우

이 경우의 수를 하나로 줄이기 위해서는 하나의 출구에서 만나게 가정하는게 좋습니다.

그래서 문제를 접근하는 첫 번째 전략은 외곽이 빈 공간으로만 이루어지게 감옥을 확장하는 것입니다.

즉 아래와 같은 감옥 평면도가 있다면

****#****
*..#.#..*
****.****
*$#.#.#$*
*********

아래처럼 확장할 수 있습니다.

...........
.****#****.
.*..#.#..*.
.****.****.
.*$#.#.#$*.
.*********.
...........

이렇게 만들면 각 외곽에는 빈 공간만 존재하기에 하나의 출구를 통해 나가는 경우만 고려하면 됩니다.

밖에서 들어오는 경우로 발상

밖으로 나가는 경우로 생각하면 고려해야 할 부분이 많습니다. 공통된 문을 최대로 사용하면서 최소의 문 개수를 구하는 것이 목표인데, 한 명의 죄수가 탈출한 후 다른 죄수가 탈출하는 경우를 고려한다면 한 죄수가 특정 문을 사용하여 탈출하는 최적 경로가 다른 죄수의 최적의 탈출 방법과 공통적으로 고려했을 때 그것은 최소가 아닐 수 있습니다. 즉 이러한 이유 때문에 1번 죄수의 하나의 경로에 2번 죄수의 모든 경로를 고려해야하는 복잡성이 생기게됩니다.

즉 두 경로 간의 효과적인 상호작용을 고려하는 알고리즘이 필요합니다.

어떻게 해결하는게 좋을까요?
반대로 생각을 해봅시다.

어처피 밖으로 나가는 경우를 고려해야하는 밖에서 안에 죄수까지 닿는 비용까지 생각을 해보는 것입니다.

즉 탈출을 하는 경우는 각 죄수마다 복합적으로 모든 출구를 고려해야하므로 매우 복잡합니다.

하지만 안에서 각 죄수에 도달하는 최소 비용은 한번의 탐색으로 그 비용이 계산 가능합니다.

즉 정리해서 말하면 감옥 밖에서 시작하는 가상의 탐색자를 한명 두어서 세 명이 최소의 비용으로 만나는 어떠한 점을 고려하기만 하면 됩니다.

무조건 탈출할 수 있는 경우만 문제에서 주어지기 때문에 감옥 평면도 내에서 벽이 아닌 모든 공간에서 탐색자, 죄수1, 죄수2는 만날 수 있게 됩니다.

이렇게 만나게 된다면 탐색자는 이미 밖에서 들어 왔기 때문에 문을 더 이상 열지 않고 왔던 길로 돌아가면 탈옥에 성공하게 됩니다.

즉 우리가 구해야할 것은 세 명 각각의 비용 합의 최소 지점입니다.

공통 지점 고려

이렇게 최소 지점을 찾았다면 또 고려해야 할 중요한 점은 그 최소 지점이 어떤 공간인지를 고려해야 합니다. 최소 지점이 빈 공간이라면 특별히 추가적인 조치를 취할 필요가 없습니다. 하지만, 만약 그 지점이 문이라면, 이 문은 세 명(두 죄수와 감옥 밖에서 시작한 탐색자)에 의해 열리게 되는 비용이 겹치게 됩니다. 이는 곧, 실제로 그 문을 열기 위한 비용이 세 번 계산되었다는 것을 의미합니다. 따라서, 비용이 중복으로 계산되지 않도록 조정해야 하며, 실제 비용을 정확하게 반영하기 위해 이 중복 비용을 제거하는 과정, 즉 -2를 해주어야 합니다.

이렇게 생각하다보면 의문이 생길 수 있습니다.
세 명이 만나기전에 이미 두 죄수에 의해 겹치게 문을 열면서 진행하여 만나는 경우도 있지 않을까?

제가 이러한 생각을 했는데 좀 더 생각해보면 이러한 경우는 사실 고려할 필요가 없습니다 왜냐하면 그런 경우는 없기 때문입니다.

최소 지점을 구했다는 의미는 그것은 이미 두 죄수가 처음으로 공통된 문을 여는 지점이라는 것입니다.

처음 공통된 문이 열렸다면 그 이후는 같이 움직이면 됩니다. 즉 문을 한번만 열면 된다는 거죠
이것은 어떻게 보면 탐색자가 그 공통된 길 만큼 감옥에 좀 더 깊이 들어와주면 된다는 것입니다.

탐색자는 한번만 들어오고 죄수들과는 정반대 방향 (밖 -> 안) 오기 때문에 되돌아가기전 까지는 죄수들과 공통으로 문을 여는 경우는 없습니다.

마지막으로 총 정리를 하자면 감옥을 확장한다음 밖에서 안으로 접근하는 탐색자를 두어 각 3명이 도달하는데 걸리는 비용, 즉 문을 열며 가는 최소 거리 배열을 3개를 따로 구해서 각 3개의 합이 최소인 지점을 구해주면 되는 것 입니다.

코드

import java.util.*

data class Point(val x: Int, val y: Int)

fun main() {
    val br = System.`in`.bufferedReader()
    val t = br.readLine().toInt()
    val sb = StringBuilder()
    repeat(t) {
        val (h, w) = br.readLine().split(" ").map { it.toInt() }

        // 감옥 평면도 확장
        val grid = Array(h + 2) { Array(w + 2) { '.' } }
        val prisoners = mutableListOf<Point>() // 죄수의 위치

        for (i in 1..h) {
            val line = br.readLine()
            for (j in 1..w) {
                // 확장된 곳 가운데에 평면도 업데이트
                grid[i][j] = line[j - 1]
                if (line[j - 1] == '$') prisoners.add(Point(i, j))
            }
        }

        // 각 시작점(죄수 2명, 감옥 밖)으로부터의 최소 문 개수를 저장할 배열
        val distances = Array(3) { Array(h + 2) { IntArray(w + 2) { Int.MAX_VALUE } } }

        // 3가지 경우에 대해 bfs 진행 독립적인 비용 배열 구함
        bfs(grid, prisoners[0], distances[0])
        bfs(grid, prisoners[1], distances[1])
        bfs(grid, Point(0, 0), distances[2])

        // 최소 문 개수를 계산
        var minDoors = Int.MAX_VALUE

        // 각 지점에 대해서 3가지 경우에 대한 비용 합 구함
        for (i in 0 until h + 2) {
            for (j in 0 until w + 2) {
                if (grid[i][j] == '*') continue
                // 최소 지점이 문이라면 중복 계산 -2
                val doors = distances.sumOf { it[i][j] } - if (grid[i][j] == '#') 2 else 0
                minDoors = minOf(minDoors, doors)
            }
        }

        sb.append(minDoors).append("\n")
    }
    print(sb.toString())
}

fun bfs(grid : Array<Array<Char>>, start : Point, distance : Array<IntArray>) {
    val moveX = arrayOf(1,-1,0,0)
    val moveY = arrayOf(0,0,1,-1)

    val queue : Queue<Point> = LinkedList()
    distance[start.x][start.y] = 0 // 시작점의 거리를 0으로 설정
    queue.add(start) // 시작점을 큐에 추가

    while (queue.isNotEmpty()) {
        val (x,y) = queue.remove()
        for (i in 0 until 4) {
            val nx = x + moveX[i]
            val ny = y + moveY[i]

            // 범위 내고 벽이 아니라면 진행
            if (nx !in grid.indices || ny !in grid[0].indices || grid[nx][ny] == '*') continue

            // 벽이라면 비용 증가
            val newDistance = distance[x][y] + if (grid[nx][ny] == '#') 1 else 0

            // 비용이 갱신된다면 q에 넣어주기
            if (newDistance < distance[nx][ny]) {
                distance[nx][ny] = newDistance
                queue.add(Point(nx, ny))
            }
        }
    }

}