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

2206번 벽 부수고 이동하기

접근 방법

처음 접근한 방법은 그래프[row][col]이 1인 경우 0으로 바꿔서 다시 bfs를 이용해 최단경로를 구하는 방법이였다.
이방법은 시간복잡도가 O(n^4)까지 되어서 시간초과가 생겼다.

이 방법에서 개선하기 위해 고민한 결과 파괴 전,후에 대한 방문 여부를 구분하는 배열을 추가하면 O(n^2)의 시간복잡도로 해결할 수 있을 것이라 생각했다.

접근 방식대로 코드를 작성하니 풀렸고, 좀더 개선할 부분을 찾아보았다.
bfs로 접근하다보니 처음 목적지에 도착한 경우가 최단경로일 수 밖에 없어서 (N,M)에 도착하면 continue가 아닌 break로 바꾸었다.

또한, 파괴를 하고 난 후에는 방문 배열이 이전의 방문 배열과 달라지므로 조금이라도 중복을 제거하고자 파괴 상태고, 파괴 배열의 값과 파괴 전 배열의 값이 둘다 false인 경우에만 추가하도록 하였다.

시간복잡도

모든 좌표를 방문하므로
O(N* M)

Code

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*

class IO2206 {
    private val br = BufferedReader(InputStreamReader(System.`in`))
    private val bw = BufferedWriter(OutputStreamWriter(System.out))

    fun getNumList() = br.readLine().split(" ").map { it.toInt() }
    fun getRow() = br.readLine()!!
    fun flush() = bw.flush()
    fun close() = bw.close()
    fun write(message: String) = bw.write(message)
}

fun main() {
    val io = IO2206()
    val (N, M) = io.getNumList()
    val graph = mutableListOf<Array<Int>>()
    repeat(N) {
        graph.add(io.getRow().map { it.toString().toInt() }.toTypedArray())
    }
    val visited = mutableListOf<Array<Array<Boolean>>>().also { list ->
        repeat(N) { list.add(Array(M) { Array(2) { false } }) }
    }

    var ans = Int.MAX_VALUE

    data class Info (val row: Int, val col: Int, val dis: Int, val destroyed: Boolean)

    val queue: Queue<Info> = LinkedList()
    queue.add(Info(0,0,1, false))
    while (queue.isNotEmpty()) {
        val (row, col, dis, destroyed) = queue.poll()

        if (row == N-1 && col == M-1) {
            ans = dis
            break
        }
        val dy = listOf(-1,1,0,0) // 상하좌우
        val dx = listOf(0,0,-1,1)
        for (idx in (0..3)) {
            val newY = row + dy[idx]
            val newX = col + dx[idx]
            if (newY < 0 || newY > N - 1 || newX < 0 || newX > M - 1) {
                continue
            }
            if (graph[newY][newX] == 0) {
                if (destroyed && !visited[newY][newX][1] && !visited[newY][newX][0]) {
                    queue.add(Info(newY, newX, dis+1, destroyed))
                    visited[newY][newX][1] = true
                } else if (!destroyed && !visited[newY][newX][0]) {
                    queue.add(Info(newY, newX, dis+1, destroyed))
                    visited[newY][newX][0] = true
                }
            } else if (graph[newY][newX] == 1) {
                if (!destroyed) {
                    queue.add(Info(newY, newX, dis+1, !destroyed))
                    visited[newY][newX][1] = true
                }
            }
        }
    }
    if (ans == Int.MAX_VALUE) ans = -1
    io.write(ans.toString())
    io.flush()
    io.close()
}