[백준 2206번] 벽 부수고 이동하기 - Kotlin

[백준 2206번] 벽 부수고 이동하기 - Kotlin

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

---

문제

• N×M의 행렬로 표현되는 맵이 있다.
• 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다.
  당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다.
• 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.
• 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.
• 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.
• 맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오

---

입력

• 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다.
• 다음 N개의 줄에 M개의 숫자로 맵이 주어진다.
• (1, 1)과 (N, M)은 항상 0이라고 가정하자

---

출력

• 첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다

---

풀이

private class Solution2206 {
    private val directions = arrayOf(
        1 to 0,
        -1 to 0,
        0 to 1,
        0 to -1
    )

    fun solution(
        n: Int,
        m: Int,
        map: Array<IntArray>
    ): Int {
        var result = Int.MAX_VALUE

        val deque = ArrayDeque<Triple<Int, Int, Int>>().apply {
            add(Triple(0, 0, 1))
        }
        val visited = Array(n) { Array(m) { IntArray(2) } }
        visited[0][0][1] = 1

        while (deque.isNotEmpty()) {
            val (row, col, chance) = deque.removeFirst()

            if (row == n - 1 && col == m - 1) {
                result = visited[row][col][chance]
                break
            }

            for (direction in directions) {
                val nextRow = row + direction.first
                val nextCol = col + direction.second

                if (nextRow !in 0 until n || nextCol !in 0 until m) {
                    continue
                }

                when (map[nextRow][nextCol]) {
                    0 -> if (visited[nextRow][nextCol][chance] == 0) {
                        deque.add(Triple(nextRow, nextCol, chance))
                        visited[nextRow][nextCol][chance] = visited[row][col][chance] + 1
                    }
                    1 -> if (chance == 1) {
                        deque.add(Triple(nextRow, nextCol, 0))
                        visited[nextRow][nextCol][0] = visited[row][col][1] + 1
                    }
                }
            }
        }


        return when (result) {
            Int.MAX_VALUE -> -1
            else -> result
        }
    }

    data class Node(
        val row: Int,
        val col: Int,
        val distance: Int,
        val isBreakWall: Boolean = false
    )

}

private fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val (n, m) = br.readLine().split(" ").map(String::toInt)
    val map = Array(n) {
        val str = br.readLine().toCharArray()
        IntArray(m) { str[it].digitToInt() }
    }

    bw.append("${Solution2206().solution(n, m, map)}\n")
    bw.flush()

    br.close()
    bw.close()
}