1261번: 알고스팟 - Kotlin (0-1 BFS)

1261번: 알고스팟

문제

알고스팟 운영진이 모두 미로에 갇혔다. 미로는 N*M 크기이며, 총 1*1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다.

알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 이다. 단, 미로의 밖으로 이동 할 수는 없다.

벽은 평소에는 이동할 수 없지만, 알고스팟의 무기 AOJ를 이용해 벽을 부수어 버릴 수 있다. 벽을 부수면, 빈 방과 동일한 방으로 변한다.

만약 이 문제가 알고스팟에 있다면, 운영진들은 궁극의 무기 sudo를 이용해 벽을 한 번에 다 없애버릴 수 있지만, 안타깝게도 이 문제는 Baekjoon Online Judge에 수록되어 있기 때문에, sudo를 사용할 수 없다.

현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다.

(1, 1)과 (N, M)은 항상 뚫려있다.

출력

첫째 줄에 알고스팟 운영진이 (N, M)으로 이동하기 위해 벽을 최소 몇 개 부수어야 하는지 출력한다.

 

 

나의 풀이 - 1차 (시간 초과)

 처음 이 문제를 접했을 때는, DFS를 이용해서 문제를 해결하려고 하였다. 적당하게 백트래킹을 통해서 n, m까지 이동하는 방법을 무차별적으로 구한다음 list에 넣어서 가장 작은 정수를 반환하도록 하였다. 하지만 이런 방식을 사용하니까 시간 초과가 발생하였다.

 

import java.util.*

val dx = arrayOf(1, 0, 0, -1)
val dy = arrayOf(0, 1, -1, 0)

val result = mutableListOf<Int>()

fun main() = with(System.`in`.bufferedReader()) {
    val (m, n) = readLine().split(" ").map { it.toInt() }

    val maze = Array(n) { readLine().map { it.toString().toInt() }.toIntArray() }

    val visited = Array(n) { BooleanArray(m) }

    dfs(0, 0, 0, n, m, maze, visited)
    println(result)
    println(result.min())
}

fun dfs(x: Int, y: Int, cnt: Int, n: Int, m: Int, maze: Array<IntArray>, visited: Array<BooleanArray>) {
    if (result.isNotEmpty() && cnt > result.min()) {
        return
    }

    if (x == n - 1 && y == m - 1) {
        result.add(cnt)
        return
    }

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

        if (tempX in 0 until n &&
            tempY in 0 until m &&
            !visited[tempX][tempY]) {
            visited[tempX][tempY] = true
            if (maze[tempX][tempY] == 0) {
                dfs(tempX, tempY, cnt, n, m, maze, visited)
            }
            else {
                if (result.isEmpty())
                    dfs(tempX, tempY, cnt + 1, n, m, maze, visited)
                else {
                    if (result.min() > cnt + 1) {
                        dfs(tempX, tempY, cnt + 1, n, m, maze, visited)
                    }
                }
            }
            visited[tempX][tempY] = false
        }
    }
}

 

나의 풀이 - 2차

 내가 이전에 풀었던 방식은 너무 비 효율적이었다. 그래서 한번에 경로를 찾을 필요가 있었다. 그래프가 있을 때, 가중치가 있다면 가장 적은 가중치로 최단 경로를 찾은 방법. 바로 다익스트라 알고리즘이다. 다익스트라 알고리즘과 유사한 방식으로 BFS를 구현할 수 있다. 그게 바로 0-1 BFS 이다. 0-1 BFS는 가중치가 0과 1일때 사용할 수 있는데, 지금이 바로 그 상황이다. 이렇게 해야 한다는 것을 안 이후로부터는 구현은 그렇게 어렵지 않다. 다만 더 빠른 알고리즘을 구현하기 위해서 아래에 보게 되면 addFirst를 통해 0일때 부터 먼저 고려하게 해 주는것이 좋다.

 

import java.util.*
import kotlin.collections.ArrayDeque

val dx = arrayOf(1, 0, 0, -1)
val dy = arrayOf(0, 1, -1, 0)

fun main() = with(System.`in`.bufferedReader()) {
    val (m, n) = readLine().split(" ").map { it.toInt() }

    val maze = Array(n) { readLine().map { it.toString().toInt() }.toIntArray() }


    bfs(n, m, maze)
}

fun bfs(n: Int, m: Int, maze: Array<IntArray>) {
    val deque = ArrayDeque<Pair<Int, Int>>()
    val visited = Array(n) { IntArray(m) { -1 } }

    deque.add(0 to 0)
    visited[0][0] = 0

    while (deque.isNotEmpty()) {
        val (x, y) = deque.removeFirst()

        if (x == n - 1 && y == m - 1) {
            println(visited[x][y])
            return
        }

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

            if (tempX in 0 until n &&
                tempY in 0 until m &&
                visited[tempX][tempY] == -1) {
                if (maze[tempX][tempY] == 0) {
                    visited[tempX][tempY] = visited[x][y]
                    deque.addFirst(tempX to tempY)
                }
                else {
                    visited[tempX][tempY] = visited[x][y] + 1
                    deque.addLast(tempX to tempY)
                }
            }
        }
    }
}