[BOJ]알고스팟 in Kotlin

문제풀러 가기!

이 문제는 사실 dfs로 접근했다가 틀린 문제입니다. 아직 입력값을 고려한 로직을 작성하는데, 문제가 있는건가 싶네요.

그리고 문제를 풀면서 하나 새로 얻은 것도 있습니다.바로 ArrayDeque()라고 하는 겁니다. 사실 Python을 먼저 배우다 보니, 이런 자료 구조에 대한 내용을 잘 모르는 경우도 있는 것 같습니다. 그래서 deque라고 하는 것을 내일 좀 더 자세히 알아보는 것으로 하겠습니다.

이 문제의 풀이는 queue를 이용하되, 벽을 뿌시지 않고 최단 거리로 이동할 수 있는 부분을 먼저 탐색합니다. 그 이후에 벽을 뿌시면서 간다고 보시면 됩니다. 그렇기 때문에 불필요한 탐색을 멈출 수 있습니다. 즉 먼저 탐색할 것은 앞으로 그렇지 않은 것은 뒤로 add하시면 됩니다.

import java.io.BufferedReader
import java.io.InputStreamReader

private val dx = arrayOf(0, 1, 0, -1)
private val dy = arrayOf(1, 0, -1, 0)

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {

    val (n, m) = readLine().split(" ").map { it.toInt() }
    val room = Array(m) {
        readLine().map { it.digitToInt() }
    }

    val visited = Array(m) {
        IntArray(n) {-1}
    }

    visited[0][0] = 0

    val deque = ArrayDeque<Node>()
    deque.addFirst(Node(0, 0))

    while (deque.isNotEmpty()) {

        val x = deque.first().x
        val y = deque.first().y
        deque.removeFirst()

        for (i in 0 until 4) {
            val nx = x + dx[i]
            val ny = y + dy[i]

            if (nx in 0 until m && ny in 0 until n) {
                if (visited[nx][ny] == -1) {
                    if (room[nx][ny] == 0) {
                        visited[nx][ny] = visited[x][y]
                        deque.addFirst(Node(nx, ny))
                    } else {
                        visited[nx][ny] = visited[x][y] + 1
                        deque.addLast(Node(nx, ny))
                    }
                }
            }
        }
    }
    println(visited[m-1][n-1])
    close()
}

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

사실 이 문제의 경우 알고리즘을 이해하기 보다는 데이터 입력 받는 데, 더 힘들었던 문제입니다.ㅋㅋㅋ 문자열을 배열로 변화해서 입력을 어떻게 받아야 할지 모르겠더군요..

digitToInt()이거 잊으면 안되겠습니다..ㅋㅋㅋㅋ