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

BFS + 3차원 배열을 활용하는 문제이다.
벽을 부수고 진행하였는지 확인할 data class 와 dx, dy 를 활용하여 다음 길에 대한 풀이를 이어나가자.

풀이

/*
* 0 -> 이동 가능, 1 -> 이동할 수 없는 벽이 존재
* (1, 1) 에서 (N, M) 까지 이동. 최단 경로로
* 시작하는 칸과 끝나는 칸도 포함해서 세야한다.
* 이동하는 도중, 한 개의 벽을 부수고 이동하는 것이 짧아지는거라면 한 개까지는 부수고 이동해도 된다.
*
* 1 <= N, M <= 1000. 입력값은 1000 * 1000 = 1_000_000
* */

/**
* @param wallBroken 이전에 벽을 파괴했는지 판단
* */
private data class State(
    val x: Int,
    val y: Int,
    var wallBroken: Int,
)

private var row = 0
private var col = 0
private val dx = intArrayOf(-1, 1, 0, 0)
private val dy = intArrayOf(0, 0, -1, 1)
private const val IS_NOT_VISIT = -1
// 0-based Index
private lateinit var map: Array<String>
private lateinit var visited: Array<Array<IntArray>>

fun `2206 - 벽 부수고 이동하기`(){
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val input = br.readLine().split(" ").map { it.toInt() }
    row = input[0]
    col = input[1]
    map = Array(row){ br.readLine() }
    visited = Array(row){ Array(col){ IntArray(2){ IS_NOT_VISIT } } }

    bw.write(bfs().toString())
    bw.flush()
    bw.close()
    br.close()
}

private fun bfs(): Int {
    val arrayDeque = ArrayDeque<State>()

    arrayDeque.addLast(State(0, 0,  0))
    visited[0][0][0] = 1

    while(arrayDeque.isNotEmpty()){
        val current = arrayDeque.removeFirst()
        val x = current.x
        val y = current.y
        val broken = current.wallBroken

        // x, y 가 도착 지점이면
        if(x == row - 1 && y == col - 1){
            return visited[x][y][broken]
        }

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

            when {
                // nx 나 ny 가 제한구역에 포함되지 않았다면 다음 순번으로 넘기기
                nx !in 0 until row || ny !in 0 until col -> continue
                // 다음 칸이 벽이고, 이미 벽을 깬 전적이 없다면
                map[nx][ny] == '1' && broken == 0 -> {
                    // 부순 상태로 다음 칸에 방문한 적이 없다면
                    if(visited[nx][ny][1] == IS_NOT_VISIT){
                        val state = State(nx, ny, 1)
                        visited[nx][ny][1] = visited[x][y][broken] + 1
                        arrayDeque.addLast(state)
                    }
                }
                // 다음 칸이 길이고, 방문한 적이 없을때
                map[nx][ny] == '0' && visited[nx][ny][broken] == IS_NOT_VISIT -> {
                    val state = State(nx, ny, broken)
                    visited[nx][ny][broken] = visited[x][y][broken] + 1
                    arrayDeque.addLast(state)
                }
            }
        }
    }

    return -1
}

후기

private data class Way(
    val isWall: Boolean,
    var isDestroyed: Boolean,
    var count: Int
){
    fun change(isDestroy: Boolean, changeCount: Int){
        isDestroyed = isDestroy
        count = changeCount
    }
}

처음에는 위와 같은 데이터 클래스를 구현하여 val map = Array<Array<dataClass>> 처럼 초기화를 진행, 이를 통해 진행상황을 나타내도록 구현하였으나, 실패하였다.

이유는 한 칸에서 나타내는 것이 벽을 부수고 진행했을때와, 벽을 부수지 않고 진행했을 때 2 가지 상황이어야 하는데 내가 표현한 방법으로는 먼저 방문한 1가지가 다른 1가지의 접근을 차단하기 때문이었다.

BFS 를 사용하는 상황마다 매번 방문 여부를 하나의 상황에서만 작성했었기 때문에 벌어지는 문제였다.

앞으로 특정한 상황이 주어지면 해당 상황을 조건으로 추가하여 풀어야겠다고 생각햇다.