[백준][Kotlin] - 보물 찾기2(다익스트라와 0-1 BFS 차이)

🥇️ 문제 레벨 : 골드3
🔔 문제 유형 : 다익스트라
💬 풀이 언어 : Kotlin
🖇️ 문제 링크 : 백준 문제 링크

💬 소개

다익스트라는 대표적으로 두 가지 방법으로 풀이할 수 있다.

• PriorityQueue를 사용한 일반 다익스트라
• Deque를 사용한 0-1 BFS

이 두 방식에 대해서 문제를 풀이하면서 한 번 알아보자.

📝 문제

 건덕이는 지난 보물찾기에서 보물을 찾는 데 성공했다. 이제는 배를 타고 세계 곳곳을 누비며 보물을 찾아 나서는 보물 탐사대가 되었다.

 

건덕이는 주변 섬들의 지형이 담긴 가로 W칸, 세로 H칸의 지도를 구했다. 지도에는 주변 바다의 지형이 나타나 있다. 바다와 암초로 이루어져 있는데, 배는 암초 위를 지나다닐 수 없다. 지도의 가장 왼쪽 위는 (1, 1), 오른쪽 아래는 (H, W)이다.

 

건덕이의 배는 매번 인접한 8칸 중 한 곳으로 이동할 수 있다. (r, c)와 인접한 칸은 max(|r-x|, |c-y|) = 1인 (x, y) 이다. 안전한 항해를 위해 지도 바깥으로는 나가지 않는다.

 

바다의 물살이 지도 기준 왼쪽에서 오른쪽으로 빠르게 흐르고 있어서, 물살을 타고 가는 데에는 연료가 들지 않지만, 그 외에는 한 칸당 1의 연료가 소모된다. 예를 들어, 건덕이가 현재 (r, c) 위치에 자리 잡고 있다면 (r-1, c+1), (r, c+1), (r+1, c+1)로는 연료 소모 없이 이동할 수 있고, 그 외의 칸으로는 1의 연료를 소모해야 한다.

 

건덕이의 손에 보물지도가 주어졌다. 보물을 찾기까지 소모해야 하는 연료의 최솟값을 구해 주자!

🤔 알고리즘 분석

이 문제는 최소한의 비용을 들여 목적지에 도달해야하는 전형적인 다익스트라 문제이다. 이 문제의 핵심은 이동 방향에 따른 가중치 차이라고 보면 될 것 같다. 정답은 맞았지만, 제출 결과를 보고 위화감을 느꼈다.

메모리 : 148536 KB (약 145MB)
시간 : 708 ms

자바로 푼 다른 사람들의 결과(평균 30MB, 300ms)에 비해 내 코드는 메모리를 5배, 시간을 2배나 더 쓰고 있었다. 단순히 언어 차이라고 하기엔 격차가 너무 컸다. 왜 이런 결과가 나왔는지 Deep dive 해보자.

시간 복잡도 비교

그래프 알고리즘에서 시간 복잡도를 논할 때, 정점의 개수인 V(Vertex), 간선의 개수인 E(Edge)를 의미한다. 즉, 이 문제인 격자판 환경은 다음과 같이 정의할 수 있다.

• V(정점의 수): 지도의 크기 (H * W)
• E(간선의 수): 각 칸에서 8방향 이동 가능(약, 8 * H * w)

다익스트라

다익스트라는 우선 순위 큐(PriorityQueue)를 사용한다.

val pq = PriorityQueue<State>(compareBy { it.cost })

pq.add(State(ny, nx, nextCost))

큐에 원소를 넣고(add), 뺄 때(poll)마다 재정렬(Heapify) 비용인 log V가 들게 된다. 이 때, 모든 간선을 확인하기 때문에, 총 시간 복잡도는 O(E log V)가 된다.

0-1 BFS

0-1 BFS는 단순하게 설명하면, 가중치가 0과 1일 때 사용할 수 있는 BFS 알고리즘이다. 이는, 우선 순위 큐 대신 ArrayDeque를 사용한다. 기본적인 아이디어는 다음과 같다.

val deque = ArrayDeque<State>()

if (add == 0) {
    deque.addFirst(State(ny, nx, nextCost))
} else {
    deque.addLast(State(ny, nx, nextCost))
}

덱(디큐)는 위, 아래가 뚫려있는 통이라고 생각하면 된다. 가중치가 0인 경우 먼저 처리하고, 가중치가 1인 경우 나중으로 미루는 것이다.

 

덱은 정렬 과정 없이 데이터를 앞 뒤로만 넣기 때문에, 삽입과 삭제는 O(1)로 굉장히 빠르다. 이 알고리즘 또한, 8방향 모두 탐색을 하므로, 총 시간 복잡도는 O(V + E)가 된다. 즉, 일반 다익스트라에 비해 log 항만큼 더 빠르다는 것이다.

메모리 사용량 비교

아무리 생각해도 PriorityQueue, Deque 모두 8방향을 탐색해서 노드를 넣는데 왜 메모리가 크게 차이가 나는지 궁금해졌다. 이를 알아내면서 알게된 가장 큰 핵심은 바로 큐에 존재하는 노드의 생명 주기와 탐색 방식 차이였다. 다음 예시를 시뮬레이션하며 알아보자.

. . . . .  
. . . . .  
. . K . .  
. . . . .  
. . . . *

여기에서 다음 방향을 찾기 위한 배열은 다음과 같이 정의되어 있으며, 1시, 3시, 5시 방향은 물살을 타기 때문에 연료 사용량(가중치)는 0이 되고, 나머지 방향은 1씩 사용한다.

// 방향 순서: 12시, 1시, 3시, 5시, 6시, 7시, 9시, 11시
val dy = intArrayOf(-1, -1, 0, 1, 1, 1, 0, -1)  
val dx = intArrayOf(0, 1, 1, 1, 0, -1, -1, -1)

다익스트라

다익스트라는 넓게 퍼진다. 즉, 현재 발견됭 경로보다 더 짧은 경로를 찾으면, 큐에 계속 추가하게 된다. 예를 들어 (3, 3)에 가는 비용 10을 큐에 넣었는데, 나중에 비용 5인 경로를 찾으면 또 넣는다. 이때 비용 10인 '쓸모없는 노드'도 본인 차례가 와서 삭제될 때까지 큐 한구석을 차지하고 있다.

 

더 중요한 점은 바로 비용이 같은 노드가 여러 개인 경우이다. Heap 구조 특성상 넣은 순서는 무시되고, 비용으로만 따지게 된다. 따라서, poll()을 호출했을 때, 비용이 0인 노드 중에 어떤 노드가 튀어나올 지 모른다.

. . . . .    . . . . .    . . 1 1 0    . . 1 1 0    . . 1 1 0  
. . . . .    . 1 1 K .    . 1 1 0 0    . 1 1 0 0    . 1 1 0 0  
. . K . . => . 1 0 0 . => . 1 0 K 0 => . 1 0 0 0 => . 1 0 0 0  
. . . . .    . 1 1 0 .    . 1 1 0 .    . 1 1 K 0    . 1 1 0 0  
. . . . *    . . . . *    . . . . *    . . . . *    . . 1 1 K

숫자는 각 좌표에 도달하기 위한 최소 연료이다.

위 예시와 같이, 최소 연료가 0인 노드 중 한 곳을 랜덤으로 가게 된다. 따라서, 다익스트라를 사용했을 때, PriorityQueue에 쌓일 수 있는 최대 노드의 수는 18개인 것이다.

0-1 BFS

0-1 BFS는 DFS와 유사하게 한 방향으로 우직하게 탐색한다. 위 설명에서 적은 것과 같이, 가중치가 0인 경우에는 addFirst를 호출하게 된다. 즉, dy, dx 배열에서 1, 2, 3번 인덱스 순서대로 addFirst를 하게 되는 것이다.

 

그렇다면, while 문을 돌면서 removeFirst()를 호출하면 누가 나올까? 3번 인덱스로 추가된 노드가 나오게 된다. 즉, 이를 계속 반복하면, 0-1 BFS는 사실상 DFS와 유사하게 한 방향으로 탐색을 할 수 있게 되는 것이다. 이 특성 때문에, Deque에는 최소한의 노드들만 쌓일 수 있게 된다.

. . . . .    . . . . .    . . . . .  
. . . . .    . 1 1 0 .    . 1 1 0 .   
. . K . . => . 1 1 0 . => . 1 1 0 0  
. . . . .    . 1 1 K .    . 1 1 0 0  
. . . . *    . . . . *    . . 1 1 K

위 예시와 같이, 가중치가 0인 노드 중 한 방향으로만 탐색하게 되는 것이다. 따라서, 0-1 BFS를 사용했을 때, ArrayDeque에 쌓일 수 있는 최대 노드의 수는 14개인 것이다. 4개 정도의 차이 뿐이지만, 지도의 크기가 최대 500 * 500임을 따지면 나중에는 굉장히 큰 차이가 나게 되는 것이다.

결론

이 문제는 두 가지 방식으로 풀 수 있지만, 가중치가 0과 1과 같이 단순한 그래프에서는 0-1 BFS 알고리즘을 채택하는게 더 효율이 좋다.

😎 최종 코드

일반 다익스트라

메모리 : 148536 KB
시간 : 708 ms

import java.util.PriorityQueue
import java.util.StringTokenizer

private const val SEA = '.'
private const val REEF = '#'
private const val TREASURE = '*'
private const val SHIP = 'K'

fun main() = with(System.`in`.bufferedReader()) {
    val (h, w) = StringTokenizer(readLine()).run {
        nextToken().toInt() to nextToken().toInt()
    }

    // 0: 배, 1: 보물
    val info = Array(2) { 0 to 0 }

    val map = Array(h) { i ->
        val line = readLine()
        CharArray(w) { j ->
            val mark = when (val cur = line[j]) {
                SHIP -> {
                    info[0] = i to j
                    SEA
                }

                TREASURE -> {
                    info[1] = i to j
                    cur
                }

                else -> cur
            }

            mark
        }
    }

    println(dijkstra(map, info, h, w))

    close()
}

private data class State(val y: Int, val x: Int, val cost: Int)

private fun dijkstra(
    map: Array<CharArray>,
    info: Array<Pair<Int, Int>>,
    h: Int,
    w: Int
): Int {
    // 12시부터 시계 방향으로 8방향
    val dy = intArrayOf(-1, -1, 0, 1, 1, 1, 0, -1)
    val dx = intArrayOf(0, 1, 1, 1, 0, -1, -1, -1)

    val pq = PriorityQueue<State>(compareBy { it.cost })
    val minCost = Array(h) { IntArray(w) { Int.MAX_VALUE } }

    val (entryY, entryX) = info[0]
    val (treasureY, treasureX) = info[1]

    minCost[entryY][entryX] = 0
    pq.add(State(entryY, entryX, 0))

    while (pq.isNotEmpty()) {
        val (y, x, cost) = pq.poll()

        if (cost > minCost[y][x]) {
            continue
        }

        if (y == treasureY && x == treasureX) {
            return cost
        }

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

            if (ny in 0 until h && nx in 0 until w && map[ny][nx] != REEF) {
                val add = when (dir) {
                    1, 2, 3 -> 0
                    else -> 1
                }
                val nextCost = cost + add

                if (minCost[ny][nx] > nextCost) {
                    minCost[ny][nx] = nextCost
                    pq.add(State(ny, nx, nextCost))
                }
            }
        }
    }
    return -1
}

0-1 BFS

메모리 : 31592 KB
시간 : 372 ms

import java.util.ArrayDeque  
import java.util.StringTokenizer  

private const val SEA = '.'  
private const val REEF = '#'  
private const val TREASURE = '*'  
private const val SHIP = 'K'  

fun main() = with(System.`in`.bufferedReader()) {  
    val (h, w) = StringTokenizer(readLine()).run {  
        nextToken().toInt() to nextToken().toInt()  
    }  

    // 0: 배, 1: 보물  
    val info = Array(2) { 0 to 0 }  

    val map = Array(h) { i ->  
        val line = readLine()  
        CharArray(w) { j ->  
            val mark = when (val cur = line[j]) {  
                SHIP -> {  
                    info[0] = i to j  
                    SEA  
                }  

                TREASURE -> {  
                    info[1] = i to j  
                    cur  
                }  

                else -> cur  
            }  

            mark  
        }  
    }  
    println(dijkstra(map, info, h, w))  

    close()  
}  

private data class State(val y: Int, val x: Int, val cost: Int)  

private fun dijkstra(  
    map: Array<CharArray>,  
    info: Array<Pair<Int, Int>>,  
    h: Int,  
    w: Int  
): Int {  
    // 12시부터 시계 방향으로 8방향  
    val dy = intArrayOf(-1, -1, 0, 1, 1, 1, 0, -1)  
    val dx = intArrayOf(0, 1, 1, 1, 0, -1, -1, -1)  

    val deque = ArrayDeque<State>()  
    val minCost = Array(h) { IntArray(w) { Int.MAX_VALUE } }  

    val (entryY, entryX) = info[0]  
    val (treasureY, treasureX) = info[1]  

    minCost[entryY][entryX] = 0  
    deque.add(State(entryY, entryX, 0))  

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

        if (cost > minCost[y][x]) {  
            continue  
        }  

        if (y == treasureY && x == treasureX) {  
            return cost  
        }  

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

            if (ny in 0 until h && nx in 0 until w && map[ny][nx] != REEF) {  
                val add = when (dir) {  
                    1, 2, 3 -> 0  
                    else -> 1  
                }  
                val nextCost = cost + add  

                if (minCost[ny][nx] > nextCost) {  
                    minCost[ny][nx] = nextCost  
                    if (add == 0) {  
                        deque.addFirst(State(ny, nx, nextCost))  
                    } else {  
                        deque.addLast(State(ny, nx, nextCost))  
                    }  
                }  
            }  
        }  
    }  
    return -1  
}