[백준/BOJ] 14442번: 벽 부수고 이동하기 2

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

14442번: 벽 부수고 이동하기 2

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 K개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

해석

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

2206번: 벽 부수고 이동하기

위의 문제와 거의 비슷한 문제이다.

차이점이라면 위의 문제는 벽을 한번만 부술 수 있고,  이 문제는 벽을 원하는 만큼 부실 수 있다는 것이다.

 

bfs를 이용하여 푸는 문제이므로 방문여부를 체크할 배열, 이동방향을 선언해준다.

private lateinit var map: Array<IntArray>
private val dx = arrayOf(1, -1, 0, 0)
private val dy = arrayOf(0, 0, 1, -1)

val visited = Array(row) { Array(col) { BooleanArray(canBreak + 1) } }

또한 큐를 선언해야 하는데, 이 때 큐가 가지고 있어야 하는 정보는 현재 위치의 x, y좌표, 벽을 몇번 부술 수 있는지, 움직인 횟수가 된다.

나는 이를 데이터 클래스로 따로 만들어 큐의 자료형으로 선언해주었다.

private data class Point(val y: Int, val x: Int, val breakCnt: Int, val cnt: Int)

val que: Queue<Point> = LinkedList()

이제 bfs를 실행하면 된다.

 

탐색하고자 하는 지역이 1(벽)이라면 부술 수 있는지를 보고, 부실 수 있다면 부시고 이동시킨다.

탐색하고자 하는 지역이 0이라면 이동만 시킨다.

if(map[nextY][nextX] == 0) {
    visited[nextY][nextX][breakCnt] = true
    que.add(Point(nextY, nextX, breakCnt, moveCnt + 1))
}
else {
    if(breakCnt > 0) {
        visited[nextY][nextX][breakCnt] = true
        que.add(Point(nextY, nextX, breakCnt - 1, moveCnt + 1))
    }
}

만약 마지막 지점까지 도착하지 못한다면 -1을 return해주면 된다.

전체적인 코드를 보면 다음과 같다.

소스 코드

import java.util.*

private lateinit var map: Array<IntArray>
private val dx = arrayOf(1, -1, 0, 0)
private val dy = arrayOf(0, 0, 1, -1)

private data class Point(val y: Int, val x: Int, val breakCnt: Int, val cnt: Int)

fun main() = with(System.`in`.bufferedReader()) {
    val (row, col, canBreak) = readLine().split(" ").map { it.toInt() }
    map = Array(row) { IntArray(col) }

    repeat(row) { i ->
        val state = readLine()
        repeat(col) { j ->
            map[i][j] = state[j] - '0'
        }
    }

    println(move(row, col, canBreak))
}

fun move(row: Int, col: Int, canBreak: Int): Int {
    val visited = Array(row) { Array(col) { BooleanArray(canBreak + 1) } }
    val que: Queue<Point> = LinkedList()
    que.add(Point(0, 0, canBreak, 1))

    while(!que.isEmpty()) {
        val nowY = que.peek().y
        val nowX = que.peek().x
        val breakCnt = que.peek().breakCnt
        val moveCnt = que.peek().cnt
        que.poll()

        if(nowY == row - 1 && nowX == col - 1) return moveCnt

        for(i in 0 until 4) {
            val nextY = nowY + dy[i]
            val nextX = nowX + dx[i]

            if(nextY in 0 until row && nextX in 0 until col && !visited[nextY][nextX][breakCnt]) {
                if(map[nextY][nextX] == 0) {
                    visited[nextY][nextX][breakCnt] = true
                    que.add(Point(nextY, nextX, breakCnt, moveCnt + 1))
                }
                else {
                    if(breakCnt > 0) {
                        visited[nextY][nextX][breakCnt] = true
                        que.add(Point(nextY, nextX, breakCnt - 1, moveCnt + 1))
                    }
                }
            }
        }
    }
    return -1
}