[백준][KOTLIN][2206] 벽 부수고 이동하기

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

2206번: 벽 부수고 이동하기

문제 풀이

1. 이중 for 문을 이용하여 벽을 하나씩 부순 후 bfs 를 탐색할 경우 시간 초과가 발생한다.

2. bfs 탐색시 visit 방문 배열을 3중 배열로 선언한다. 1st Index : N, 2nd Index : M, 3rd Index : 벽돌 부순 유무

3. 처음 시작 지점(1, 1) 은 벽돌 부순 유무를 모두 true 로 설정한다.

4. queue 에는 현재 좌표(x, y), 현재 이동 횟수(초기 값은 1로 넣는다.), 현재 벽돌 부순 횟수를 저장한다.

5. 현재 벽돌 부순 회수가 0이고 map[X][Y] 가 1일 경우 벽돌을 부순 것으로 업데이트 하고 queue 저장한다.

6. 결과 출력 시 result 가 INT.MAX_VALUE 와 같을 경우 -1을 출력한다.

코드

import java.io.*
import java.util.*

private var result = Int.MAX_VALUE

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (N, M) = br.readLine().split(" ").map { it.toInt() }
    val map = Array(N + 1) { IntArray(M + 1) { 0 } }
    val brokenMap = Array(N + 1) { BooleanArray(M + 1) { false } }

    repeat(N) { index ->
        br.readLine().forEachIndexed { index2, c ->
            map[index + 1][index2 + 1] = c.digitToInt()

            if (c.digitToInt() == 1) {
                brokenMap[index + 1][index2 + 1] = true
            }
        }
    }
    bfs(N, M, map)

    if (result == Int.MAX_VALUE) println(-1) else println(result)
}
private fun bfs(N: Int, M: Int, map: Array<IntArray>) {
    val queue = LinkedList<Map2206>()
    queue.add(Map2206(1, 1, 1, 0))
    val visit = Array(N + 1) { Array(M + 1) { BooleanArray(2) { false } } }
    visit[1][1][0] = true
    visit[1][1][1] = true

    while (queue.isNotEmpty()) {
        val (curX, curY, curCount, curBroken) = queue.pop()

        if (curX == N && curY == M) {
            result = Math.min(result, curCount)
        }

        val dX = intArrayOf(-1, 1,  0, 0)
        val dY = intArrayOf( 0, 0, -1, 1)

        for (i in 0..3) {
            val nX = curX + dX[i]
            val nY = curY + dY[i]

            // 범위 밖.
            if ((nX < 1 || nX > N) || (nY < 1 || nY > M)) continue
            // 이미 방문한 장소.
            if (visit[nX][nY][curBroken]) continue

            if (map[nX][nY] == 1) {
                if (curBroken == 0) {
                    visit[nX][nY][1] = true
                    queue.add(Map2206(nX, nY, curCount + 1, 1))
                }

                continue
            }

            visit[nX][nY][curBroken] = true
            queue.add(Map2206(nX, nY, curCount + 1, curBroken))
        }
    }
}

private data class Map2206(val x: Int, val y: Int, val count: Int, val broken: Int)