[Kotlin] 프로그래머스 level2 - 배달

프로그래머스 level2 - 배달(Summer/Winter Coding(~2018))

https://school.programmers.co.kr/learn/courses/30/lessons/12978

프로그래머스

 

문제

 

풀이

import java.util.PriorityQueue

class Delivery {

    data class Node(val node: Int, val dist: Int): Comparable<Node>{
        override fun compareTo(other: Node): Int = dist - other.dist
    }

    fun solution(N: Int, road: Array<IntArray>, k: Int): Int {
        var answer = 0
        var adj = Array<MutableList<Node>>(51){ mutableListOf() }
        var dist = Array<Int>(road.size) { Int.MAX_VALUE }

        road.forEach {
            adj[it[0]].add(Node(it[1], it[2]))
            adj[it[1]].add(Node(it[0], it[2]))
        }

        dijkstra(adj, dist)

        dist.forEach {
            if(it <= k){
                answer++
            }
        }

        return answer
    }

    fun dijkstra(adj: Array<MutableList<Node>>, dist: Array<Int>){
        val q = PriorityQueue<Node>()

        dist[1] = 0
        q.offer(Node(1, 0))

        while (q.isNotEmpty()){
            val temp = q.poll()
            val cNode = temp.node
            val cDist = temp.dist

            if(dist[cNode] < cDist)
                continue

            adj[cNode].forEach {
                val nNode = it.node
                val nDist = it.dist + cDist

                if(nDist < dist[nNode]){
                    q.offer(Node(nNode, nDist))
                    dist[nNode] = nDist
                }
            }
        }

    }
}

 

우선 문제를 처음 보자마자 든 생각은 최단 경로 알고리즘 중 Dijkstra 알고리즘이 떠올랐다.

 

Dijkstra 알고리즘은 쉽게 말해서 가중치가 존재하는 그래프에서의 최단 경로를 찾는 알고리즘이다.

 

Dijkstra 알고리즘이 무엇인지 모르는 분들은 해당 게시글을 보고 오면 이해하기 쉽습니다!

https://anjji.tistory.com/10

[최단경로 알고리즘] Dijkstra(다익스트라) 알고리즘

 

해당 문제가 Dijkstra의 기초만 알아도 바로 풀리는 문제였기에 딱히 어려움은 없었다

 

while (q.isNotEmpty()){
      val temp = q.poll()
      val cNode = temp.node
      val cDist = temp.dist

      if(dist[cNode] < cDist)
          continue

      adj[cNode].forEach {
          val nNode = it.node
          val nDist = it.dist + cDist

          if(nDist < dist[nNode]){
              q.offer(Node(nNode, nDist))
              dist[nNode] = nDist
          }
      }
  }

코드에서의 핵심은 우선순위 큐를 사용하여 최소거리의 노드를 선택하고 선택한 노드를 통해서 dist 배열을 최단 경로로 수정해 나가는 것이다.

 

if(dist[cNode] < cDist)
    continue

 

위의 코드에서 cDist 즉, 현재 노드의 경로가 dist 배열의 경로보다 크다는 것은 이미 처리가 된 노드라는 뜻이기에 Pass하여 다음 노드를 검사한다.