백준 1965번 벽 부수고 이동하기 3 Kotlin

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

문제

---

생각하기

---

• BFS 문제이다.

• 생각보다 까다롭다..

동작

        for (i in 0 until 4) {
            val nX = dirX[i] + cur.x
            val nY = dirY[i] + cur.y

            if (!isAbleCheck(nX, nY)) continue

            if (board[nX][nY] == 1 && cur.brokenCount + 1 <= K) {
                if (cur.isDay) {
                    if (memo[nX][nY][cur.brokenCount + 1] > memo[cur.x][cur.y][cur.brokenCount] + 1) {
                        memo[nX][nY][cur.brokenCount + 1] = memo[cur.x][cur.y][cur.brokenCount] + 1
                        que.addFirst(Coordinate(nX, nY, cur.brokenCount + 1, memo[nX][nY][cur.brokenCount + 1], false))
                    }
                } else {
                    if (memo[nX][nY][cur.brokenCount + 1] > memo[cur.x][cur.y][cur.brokenCount] + 2) {
                        memo[nX][nY][cur.brokenCount + 1] = memo[cur.x][cur.y][cur.brokenCount] + 2
                        que.addFirst(Coordinate(nX, nY, cur.brokenCount + 1, memo[nX][nY][cur.brokenCount + 1], false))
                    }
                }
            } else if (board[nX][nY] == 0) {
                if (memo[nX][nY][cur.brokenCount] > memo[cur.x][cur.y][cur.brokenCount] + 1) {
                    memo[nX][nY][cur.brokenCount] = memo[cur.x][cur.y][cur.brokenCount] + 1
                    que.addFirst(Coordinate(nX, nY, cur.brokenCount, memo[nX][nY][cur.brokenCount], !cur.isDay))
                }
            }
        }

BFS에서 이동하는 부분은 사실 다 똑같은데 핵심은 낮에만 벽을 부수는게 가능한게 핵심인 것 같습니다.

board[nX][nY] == 1벽을 마주하고, 부술 수 있는 횟수가 남아있을경우 앞으로 나아가면 되는데,
만약 밤일 경우 그자리에서 대기해야하므로 + 2를 해준다. 낮이라면 기다릴 필요가 없으므로 그냥 가면 되니까 + 1을 해줬습니다.

0의 경우는 그냥 진행하면 됩니다.

이 문제가 어렵다고 생각한다면, SWEA의 수영장 결승전이었나 그 문제랑 유형이 굉장히 비슷해서 좀 도움이 되지 않을까 싶습니다.

결과

코드

---

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

// input
private var br = System.`in`.bufferedReader()

// variables
private var N = 0
private var M = 0
private var K = 0
private lateinit var board: Array<IntArray>


private const val INF = Int.MAX_VALUE / 2
private val dirX = intArrayOf(-1, 0, 1, 0)
private val dirY = intArrayOf(0, 1, 0, -1)

private data class Coordinate(var x: Int, var y: Int, var brokenCount: Int, var count: Int, var isDay: Boolean)

fun main() {
    val bw = System.out.bufferedWriter()

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    val ret = BFS()
    if (ret == INF) {
        sb.append(-1)
    } else {
        sb.append(ret)
    }

    return sb.toString()
} // End of solve()

private fun BFS(): Int {
    val que = ArrayDeque<Coordinate>()
    var ans = INF
    val memo = Array(N) { Array(M) { IntArray(K + 1) { INF } } }
    
    que.addFirst(Coordinate(0, 0, 0, 1, true))
    memo[0][0][0] = 1

    while (que.isNotEmpty()) {
        val cur = que.removeLast()

        if (memo[cur.x][cur.y][cur.brokenCount] < cur.count) continue

        if (cur.x == N - 1 && cur.y == M - 1) {
            ans = Math.min(ans, cur.count)
            continue
        }

        for (i in 0 until 4) {
            val nX = dirX[i] + cur.x
            val nY = dirY[i] + cur.y

            if (!isAbleCheck(nX, nY)) continue

            if (board[nX][nY] == 1 && cur.brokenCount + 1 <= K) {
                if (cur.isDay) {
                    if (memo[nX][nY][cur.brokenCount + 1] > memo[cur.x][cur.y][cur.brokenCount] + 1) {
                        memo[nX][nY][cur.brokenCount + 1] = memo[cur.x][cur.y][cur.brokenCount] + 1
                        que.addFirst(Coordinate(nX, nY, cur.brokenCount + 1, memo[nX][nY][cur.brokenCount + 1], false))
                    }
                } else {
                    if (memo[nX][nY][cur.brokenCount + 1] > memo[cur.x][cur.y][cur.brokenCount] + 2) {
                        memo[nX][nY][cur.brokenCount + 1] = memo[cur.x][cur.y][cur.brokenCount] + 2
                        que.addFirst(Coordinate(nX, nY, cur.brokenCount + 1, memo[nX][nY][cur.brokenCount + 1], false))
                    }
                }
            } else if (board[nX][nY] == 0) {
                if (memo[nX][nY][cur.brokenCount] > memo[cur.x][cur.y][cur.brokenCount] + 1) {
                    memo[nX][nY][cur.brokenCount] = memo[cur.x][cur.y][cur.brokenCount] + 1
                    que.addFirst(Coordinate(nX, nY, cur.brokenCount, memo[nX][nY][cur.brokenCount], !cur.isDay))
                }
            }
        }
    }

    return ans
} // End of BFS()

private fun isAbleCheck(x: Int, y: Int): Boolean {
    return x in 0 until N && y in 0 until M
} // End of isAbleCheck()

private fun input() {
    StringTokenizer(br.readLine()).run {
        N = nextToken().toInt()
        M = nextToken().toInt()
        K = nextToken().toInt()
    }

    board = Array(N) {
        val temp = br.readLine().toCharArray()

        IntArray(M) {
            temp[it].digitToInt()
        }
    }
} // End of input()