[백준] 2178 - 미로 탐색

'최소칸' 을 찾아야하고 인접칸으로 이동할 수 있으므로 BFS 를 활용해야하는 문제이다.
다만, 지금까지와는 달리 움직이는 칸 수를 측정해야하므로 visitedArr 에 Count 를 넣어주자.

풀이

/*
* 인접한 칸으로 이동. 최소 칸을 찾아야 함. 최소칸을 찾으므로 BFS 사용.
* 인접한 곳으로 움직여야하므로 dx, dy 변수 설정.
* 1, 1(0, 0) 에서 출발. 출발도 1칸으로 침.
*
* 움직인 최소 칸을 찾아야하므로 visited 에 count 를 넣어주고 움직이면 이전 카운트 + 1 해준다.
* */
private val dx = intArrayOf(-1, 1, 0, 0)
private val dy = intArrayOf(0, 0, -1, 1)
private lateinit var visitedArr: Array<IntArray>
private lateinit var wayArr: Array<CharArray>
private var n = 0
private var m = 0

fun `2178-미로 탐색`(){
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val token = java.util.StringTokenizer(br.readLine())

    n = token.nextToken().toInt()
    m = token.nextToken().toInt()

    // 0-based Index
    wayArr = Array(n){ br.readLine().toCharArray() }
    visitedArr = Array(n){ IntArray(m) }

    bfs()

    bw.write(visitedArr[n - 1][m - 1].toString())
    bw.flush()
    bw.close()
    br.close()
}

private fun bfs(){
    val arrayDeque = ArrayDeque<Pair<Int, Int>>()
    val startX = 0
    val startY = 0

    arrayDeque.add(startX to startY)
    visitedArr[startX][startY] = 1

    while(arrayDeque.isNotEmpty()){
        val from = arrayDeque.removeFirst()
        val x = from.first
        val y = from.second

        // 도착했으므로 종료
        if(x == n && y == m) break

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

            if(nx in 0 until n && ny in 0 until m && wayArr[nx][ny] == '1' && visitedArr[nx][ny] == 0){
                /*
                * 움직였으므로 이전 Count + 1 을 해준다.
                * */
                visitedArr[nx][ny] = visitedArr[x][y] + 1
                arrayDeque.addLast(nx to ny)
            }
        }
    }
}

후기

visitedArr 에 방문처리할 생각만했지, Count 를 넣을 생각을 못했다.
그래서 처음에는 rightBfs, bottomBfs 라는 말도 안되는 방법을 생각했는데, 당연하게도 틀려버렸다. (아주 잘못된 방법이었으므로 ...)

결국 AI 에게 도움을 빌려 움직일때마다 이전 Count 를 증가시키라는 힌트를 얻었고 이것을 응용해서 문제를 풀 수 있었다.

사고의 전환에 대해 깊게 생각하게 된 문제...