[백준 1261번] [Kotlin] 알고스팟

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

1261번: 알고스팟

 

난이도 : 골드 4
태그 : 그래프 이론, 그래프 탐색, 데이크스트라, 0-1 너비 우선 탐색

 

 

설명

시작점 (0,0)에서 도착점 (n,m)으로 가려면 얼마나 많은 벽을 부셔야 하는지 구하는 문제입니다.

특이하게도 시작점에서 도착점으로 가는 비용이나 거리가 아닌,

얼마나 많은 벽을 부셔야 하는가를 구하는 문제입니다만,

최단 경로 하면 떠오르는 BFS, 다익스트라를 응용하여 풀 수 있습니다.

 

저는 너비 우선 탐색(BFS)를 조금 변형시킨 0-1 너비 우선 탐색을 사용하여 풀겠습니다.

 

 

 

0-1 너비 우선 탐색

0-1 너비 우선 탐색은 이름에서 알 수 있듯이 BFS의 파생 탐색 기법으로써,

가중치가 0 또는 1인 그래프에서 최단 경로를 찾기 위해 사용되는 그래프 탐색 기법입니다.

 

우선순위 큐(Priority Queue) 혹은 데큐(Deque)를 사용해 구현할 수 있으며,

우선순위 큐를 사용할 경우, 간선의 가중치가 적은 순으로 정렬하여 비용이 0인 간선을 우선적으로 탐색합니다.

데큐(Deque)를 사용할 경우, 간선의 가중치가 0일 경우 큐의 앞 부분에, 가중치가 1일 경우 큐의 뒷 부분에 삽입함으로써,

마찬가지로 가중치가 0인 간선을 우선적으로 탐색합니다.

 

간선의 가중치에 따라 우선적으로 탐색한다는 점에서,

우선순위 큐 버전의 다익스트라와 비슷한 아이디어를 갖고 있다고 볼 수 있습니다.

 

이 문제에서는 벽이 없는 빈 방은 가중치를 0으로 두고,

벽이 있는 칸은 가중치를 1로 둠으로써,

빈 방을 우선적으로 탐색하고, 더 이상 탐색할 수 있는 빈 방이 없을 때에만 벽이 있는 칸을 탐색합니다.

벽이 있는 칸을 지날 때에만 비용을 1씩 증가시키면서 도착점에 도달한다면,

[시작점부터 도착점까지 지나온 벽의 개수 = 비용]이 됩니다.

 

 

 

소스코드

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

    val map = Array(n) { readLine().toCharArray().map { it.digitToInt() } }
    val q = ArrayDeque<Triple<Int, Int, Int>>()

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

    val visited = Array(n) { BooleanArray(m) }
    visited[0][0] = true
    q.add(Triple(0, 0, 0))

    while (q.isNotEmpty()) {
        val cur = q.removeFirst()

        for (i in 0 until 4) {
            val nx = cur.first + dx[i]
            val ny = cur.second + dy[i]

            if (nx !in 0 until n || ny !in 0 until m || visited[nx][ny]) continue
            visited[nx][ny] = true

            if (map[nx][ny] == 0) {
                q.addFirst(Triple(nx, ny, cur.third))
            } else {
                q.addLast(Triple(nx, ny, cur.third + 1))
            }

            if (nx == n - 1 && ny == m - 1) {
                println(cur.third)
                return
            }
        }
    }

    println(0)
}

 

 

 

 

후기

'도착점까지 가려면 부셔야 하는 최소한의 벽의 개수'라는 다소 독특한 최단경로 문제였습니다.

역시 그래프는 재밌습니다.