[백준][코틀린][16933] 벽 부수고 이동하기 3

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

16933번: 벽 부수고 이동하기 3

문제 풀이

1. BOJ14442 번에서 낮과 밤의 조건이 추가된 문제이다.

2. 처음 접근시 BOJ14442 에서 방문 여부를 확인하는 3중 visit 배열에서 마지막에 낮/밤을 확인하는 배열을 추가하여 4중 배열로 선언했다.

3. 4중 배열로 선언할 경우 결과가 메모리 초과가 발생한다.

4. 3중 배열로 선언하고 낮과 밤에 대한 조건에 대해서 벽을 만나고 밤일 경우 Queue 에 (현재 위치, 낮, 현재까지 부순 벽돌 수, Distance + 1) 을 저장하고 처리하니 이번에는 시간초과가 발생했다.

5. 다른 블로그들을 참고해서 새로운 접근법을 시도하였다.

6. broken 2중 Int 배열을 선언하고 검색하는 위치까지 부순 벽둘의 수를 저장한다.

7. 이때 제일 중요한 부분이 Queue 에 저장된 현재까지 부순 벽돌 수(curBrokenCnt) 가 broken[newX][newY] 보다 크거나 같다면 다음 탐색을 한다.

8. 지금까지 부순 벽돌보다 작은 회수의 위치는 탐색할 필요가 없기 때문이다.

코드

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

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

    repeat(N) { index1 ->
        br.readLine().forEachIndexed { index2, c ->
            map[index1 + 1][index2 + 1] = c - '0'
        }
    }

    println("${bfs(N, M, K, map)}")
}

private fun bfs(N: Int, M: Int, K: Int, map: Array<IntArray>): Int {
    val queue = LinkedList<Map16933>()
    // day -> 0 이 낮이고 1 을 밤으로 표현 한다.
    queue.add(Map16933(1, 1, 0, 0, 1))
    val broken = Array(N + 1) { IntArray(M + 1) { Int.MAX_VALUE } }
    broken[1][1] = 0

    while (queue.isNotEmpty()) {
        val (curX, curY, curNight, curBrokenCnt, curDistance) = queue.pop()

        if (curX == N && curY == M) {
            return curDistance
        }

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

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

            //범위 밖.
            if ((newX < 1 || newX > N) || (newY < 1 || newY > M)) continue
            if (broken[newX][newY] <= curBrokenCnt) continue
            //이미 방문한 영역.
            //if (visit[curBrokenCnt][newX][newY][curNight]) continue

            if (map[newX][newY] == 1) {
                if (curBrokenCnt >= K) continue

                if (curNight == 0) {
                    broken[newX][newY] = curBrokenCnt + 1
                    queue.add(Map16933(newX, newY, 1, curBrokenCnt + 1, curDistance + 1))
                } else {
                    queue.add(Map16933(curX, curY, 0, curBrokenCnt, curDistance + 1))
                }
            } else {
                broken[newX][newY] = curBrokenCnt
                queue.add(Map16933(newX, newY, 1 - curNight, curBrokenCnt, curDistance + 1))
            }
        }
    }

    return -1
}

private data class Map16933(val x: Int, val y: Int, val night: Int, val brokenCnt: Int, val distance: Int)