[백준] 2178번: 미로 탐색 - Kotlin[코틀린]

문제

 

2178번: 미로 탐색

 

---

풀이

 

 입력받은 그래프를 너비 우선 탐색(BFS)을 이용해 풀이하면 된다. BFS로 풀이할 때, 일반적으로는 graph와 같은 크기로 Boolean 배열인 visited를 만들고 방문 체크를 해준다. 그렇지만 이번 문제에서는 visited를 사용하지 않았고, graph[x][y]가 1일 때만 graph[x][y]를 갱신해주는 방법을 이용하였다. graph[x][y]가 0인 경우(벽)와 1 이상인 경우(이미 방문함)에는 방문하지 않기 때문에 최단거리를 알 수 있다.

 

---

코드

 

import java.util.LinkedList
import java.util.Queue

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

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

    val dx = arrayOf(0,1,0,-1) // x 이동 방향
    val dy = arrayOf(1,0,-1,0) // y 이동 방향

    val (rows, cols) = br.readLine().split(' ').map { it.toInt() }
    val graph = Array(rows){ IntArray(cols) }

    for(i in 0 until rows) {
        val tmp = br.readLine()
        for(j in 0 until cols) {
            graph[i][j] = tmp[j] - '0'
        }
    }

    fun bfs(x: Int, y: Int) {
        val queue : Queue<Point> = LinkedList()
        queue.offer(Point(x, y))

        while (queue.isNotEmpty()) {
            val tmp = queue.poll()
            val tx = tmp.x
            val ty = tmp.y

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

                if(nx < 0 || nx >= rows || ny < 0 || ny >= cols) continue

                if(graph[nx][ny]==1) { // graph가 1일 때만 갱신
                    graph[nx][ny] = graph[tx][ty] + 1
                    queue.add(Point(nx, ny))
                }
            }
        }
    }

    bfs(0, 0)

    bw.write("${graph[rows-1][cols-1]}")
    bw.flush()
    bw.close()
    br.close()
}