[백준] 2206. 벽 부수고 이동하기 (Kotlin)

문제

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

2206번: 벽 부수고 이동하기

 

풀이

0. 문제 해석

일단 가중치가 없는 최단경로를 구하는 문제이므로 BFS를 사용해야 한다.

 

이제 벽을 한 개까지 부술 수 있다는 조건을 어떻게 활용해야 할지 고민해보아야 하는데

일반적인 BFS 처럼 방문처리를 하게 되면 벽을 부수고 방문한 곳인지, 부수지 않고 방문한 것인지 확인할 수 없다.

 

따라서 방문배열을 3차원으로 선언하여

두 개의 공간을 만들어줘서 각각 체크해야 한다.

 

또한 현재 위치 정보를 저장하기 위한 class를 하나 만들어준다. 

distance는 현재 경로까지의 거리를 저장하고 flag는 벽을 부순 적이 있는지 저장한다.

 

이제 4방향 탐색을 시작하면서

 

1. 범위 벗어나는지 체크 -> 예외처리
2. 벽인지 체크 -> 지금 탐색하면서 아직 부순 적이 없고, 부수고 방문한 적이 없는 곳이면 탐색, 아니면 예외처리
3. 이미 방문했는지 체크 -> 예외처리
4. 경로 탐색

 

위 과정을 거쳐 정답을 구할 수 있다.

 

1. 전체 코드

// [백준] 2206. 벽 부수고 이동하기 (Kotlin)
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

data class Pair(var row: Int, var col: Int, var distance: Int, var flag: Int)

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){

    // 상하좌우
    val dx = arrayOf(-1, 1, 0, 0)
    val dy = arrayOf(0, 0, -1, 1)

    val (n,m) = readLine().split(" ").map { it.toInt() }
    val map = Array(n) { Array(m) { 0 } }

    // 방문 배열 (false = 안 부수고 방문한 곳, true = 부순 이후 방문한 곳)
    val visit = Array(n) { Array(m) { Array(2) {false} } } 
    var queue = LinkedList<Pair>()

    // 입력
    for(i in 0 until n){
        val str = readLine()
        for(j in 0 until m){
            map[i][j] = str[j] - '0'
        }
    }

    queue.offer(Pair(0,0,1,0))
    visit[0][0][0] = true
    visit[0][0][1] = true

    // bfs
    while(queue.isNotEmpty()){
        val cur = queue.poll()

        if(cur.row == n - 1 && cur.col == m - 1){
            println(cur.distance)
            return
        }

        for(i in 0 until 4){
            val nextRow = cur.row + dx[i]
            val nextCol = cur.col + dy[i]
            val flag = cur.flag
            val distance = cur.distance

            // 범위 벗어나면
            if(nextRow < 0 || nextCol < 0 || nextRow >= n || nextCol >= m){
                continue
            }

            // 벽이라면
            if(map[nextRow][nextCol] == 1){
                // 탐색하면서 아직 부순적이 없고, 부순 경로에서 방문한 적이 없던 곳이라면 탐색
                if(flag == 0 && !visit[nextRow][nextCol][1]){
                    visit[nextRow][nextCol][1] = true // 부순 경로에서 방문 처리
                    queue.offer(Pair(nextRow, nextCol, distance + 1, 1))
                }
                continue
            }

            // 이미 방문했다면
            if(visit[nextRow][nextCol][0] && flag == 0){
                continue
            }

            // 이미 방문했다면
            if(visit[nextRow][nextCol][1] && flag == 1){
                continue
            }

            visit[nextRow][nextCol][flag] = true
            queue.offer(Pair(nextRow,nextCol,distance + 1, flag))
        }
    }
    println(-1)
}