[백준] 2178번: 미로 탐색 - kotlin

문제

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

풀이

• BFS
• (0, 0) 좌표를 트리의 루트라고 생각하고,
• (n-1, m-1) 좌표를 해당 트리에 연결되어 있는 노드라고 생각하면,
• 결국 해당 노드의 트리 높이를 구하는 문제와 동일하다.
• 그러므로, BFS 알고리즘을 사용하여 해당 좌표에 도달한 값을 출력하면 된다.

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

fun bfs(n: Int, m: Int, maze: MutableList<List<Int>>): Int {
    val dx = listOf(1, -1, 0, 0)
    val dy = listOf(0, 0, 1, -1)
    val queue = mutableListOf<Point>()
    queue.add(Point(0, 0))
    val visited = Array(n) { Array(m) { 0 } }
    visited[0][0] = 1

    while (queue.isNotEmpty()) {
        val point = queue.removeFirst()
        for (i in 0..3) {
            val nx = point.x + dx[i]
            val ny = point.y + dy[i]
            if (nx in 0 until m && ny in 0 until n && visited[ny][nx] == 0 && maze[ny][nx] == 1) {
                visited[ny][nx] = visited[point.y][point.x] + 1
                queue.add(Point(nx, ny))
            }
        }
    }
    return visited[n - 1][m - 1]
}

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val (n, m) = br.readLine().split(" ").map { it.toInt() }
    val maze = mutableListOf<List<Int>>()
    repeat(n) {
        maze.add(br.readLine().split("").filter { it.isNotBlank() }.map { it.toInt() })
    }
    bw.write("${bfs(n, m, maze)}")
    br.close()
    bw.close()
}

더 좋은 방법 있으면 댓글 달아주세요!!!