Dijkstra Algorithm (다익스트라 알고리즘) with 프로그래머스 - 배달

다익스트라 알고리즘이란?

---

다익스트라 알고리즘은 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는알고리즘이다. 가능한 적은 비용으로 가장 빠르게 해답에 도달하는 경로를 찾아내는 대부분의 문제에 응용된다. 처음 고안되었을때의 다익스트라 알고리즘은 O(N²)의 시간복잡도를 가진다. 이후에 PriorityQueue 를 이용해서 O(NlogN) 까지 시간복잡도를 줄이는 방식이 고안되었다.

 

 

다익스트라 알고리즘은 다음과 같다. (P[A][B]는 A와 B 사이의 거리라고 가정한다.

출발점으로부터의 최단거리를 저장할 배열 d[v]를 만들고, 출발 노드에는 0을, 출발점을 제외한 다른 노드들에는 매우 큰 값 INF를 채워 넣는다. (정말 무한이 아닌, 무한으로 간주될 수 있는 값을 의미한다.) 보통은 최단거리 저장 배열의 이론상 최대값에 맞게 INF를 정한다. 실무에서는 보통 d의 원소 타입에 대한 최대값으로 설정하는 편.  현재 노드를 나타내는 변수 A에 출발 노드의 번호를 저장한다.  A로부터 갈 수 있는 임의의 노드 B에 대해, d[A] + P[A][B]와 d[B]의 값을 비교한다. INF와 비교할 경우 무조건 전자가 작다.  만약 d[A] + P[A][B]의 값이 더 작다면, 즉 더 짧은 경로라면, d[B]의 값을 이 값으로 갱신시킨다.  A의 모든 이웃 노드 B에 대해 이 작업을 수행한다.  A의 상태를 "방문 완료"로 바꾼다. 그러면 이제 더 이상 A는 사용하지 않는다.  "미방문" 상태인 모든 노드들 중, 출발점으로부터의 거리가 제일 짧은 노드 하나를 골라서 그 노드를 A에 저장한다.  도착 노드가 "방문 완료" 상태가 되거나, 혹은 더 이상 미방문 상태의 노드를 선택할 수 없을 때까지, 3~7의 과정을 반복한다.

 이 작업을 마친 뒤, 도착 노드에 저장된 값이 바로 A로부터의 최단 거리이다. 만약 이 값이 INF라면, 중간에 길이 끊긴 것임을 의미한다. 

 

  다익스트라 알고리즘을 실제로 구현하기에 너무 좋은 문제가 있어서 PriorityQueue를 이용한 방식으로 위의 작업을 따라서 구현해보고자 한다.

프로그래머스 - 배달

---

 

프로그래머스

문제 설명

N개의 마을로 이루어진 나라가 있습니다. 이 나라의 각 마을에는 1부터 N까지의 번호가 각각 하나씩 부여되어 있습니다. 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다. 도로를 지날 때 걸리는 시간은 도로별로 다릅니다. 현재 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 합니다. 각 마을로부터 음식 주문을 받으려고 하는데, N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려고 합니다. 다음은 N = 5, K = 3인 경우의 예시입니다.

위 그림에서 1번 마을에 있는 음식점은 [1, 2, 4, 5] 번 마을까지는 3 이하의 시간에 배달할 수 있습니다. 그러나 3번 마을까지는 3시간 이내로 배달할 수 있는 경로가 없으므로 3번 마을에서는 주문을 받지 않습니다. 따라서 1번 마을에 있는 음식점이 배달 주문을 받을 수 있는 마을은 4개가 됩니다.
마을의 개수 N, 각 마을을 연결하는 도로의 정보 road, 음식 배달이 가능한 시간 K가 매개변수로 주어질 때, 음식 주문을 받을 수 있는 마을의 개수를 return 하도록 solution 함수를 완성해주세요.

 

나의 풀이

아래의 코드는 위에 있는 다익스트라 알고리즘의 순서에 따라서 그대로 구현한 코드이다. 다만 여기선 말했던대로 PriorityQueue를 사용했기 때문에 방문 완료를 표기하는 부분은 따로 안해도 PriorityQueue안에서 poll한 순간 그 노드는 더 이상 방문하지 않게 된다.  그리고 PriorityQueue안에 Node라는 data class를 형식을 넣어주고 있어서 어느 기준으로 비교해야 하는지 PriorityQueue는 따로 정의를 해주지 않으면 알 수 없음으로 Comparable 클래스의 compareTo를 오버라이드 해서 기준점을 정해주어야 한다. 

import java.util.PriorityQueue

class Solution {
    data class Node(val index:Int, val distance:Int):Comparable<Node>{
        override fun compareTo(other:Node):Int = this.distance.compareTo(other.distance)
    }
    fun solution(N: Int, road: Array<IntArray>, k: Int): Int {
        val town = IntArray(N + 1){ 500001 }.apply{ this[1] = 0 }
        val pq = PriorityQueue<Node>().apply{ offer(Node(1, 0)) }

        while(pq.isNotEmpty()){
            val now = pq.poll()
            if(now.distance > town[now.index]) continue
            for(i in road.indices){
                if(road[i][0] == now.index){
                    val cost = now.distance + road[i][2]
                    val idx = road[i][1]
                    if(cost < town[idx]){
                        town[idx] = cost
                        pq.offer(Node(idx, cost))
                    }
                }
                else if(road[i][1] == now.index){
                    val cost = now.distance + road[i][2]
                    val idx = road[i][0]
                    if(cost < town[idx]){
                        town[idx] = cost
                        pq.offer(Node(idx, cost))
                    }
                }
            }
        }
        return town.count{ it <= k }
    }
}

 

Reference

다익스트라 알고리즘 - 나무위키

 

[ 프로그래머스 - Kotlin ] 배달 ( 코틀린 )