배달

🔒 문제

🧠 생각의 흐름

그래프 내에서 '1' 노드를 출발점으로
모든 정점까지의 최단 경로를 구하여 기준 거리값 K 이하의 노드가 배달 가능한 범위에 속한다

=> 모든 정점까지 최단경로 == Dijkstra

다익스트라

(1) 모든 정점에 대한 경로 비용 테이블을 생성한다.
🟥 이 문제에선 출발점이 '1'번 노드로 고정이고, 배열의 index 를 출발노드 번호로하기 때문에 0번 노드는 없다고 가정한다.

🟥 1을 제외한 모든 노드의 경로비용은 무한대로 초기화한다.

(2) 노드를 연결시킨다.
노드별 연결 노드를 관리하기 위해 인접 리스트(adjacentList)를 사용한다.
cycle이 허용된 undirected graph 므로 양방향 모두 연결시킨다.

(3) 최단 경로 노드부터 방문하기 위해 SortedSet 자료구조를 사용한다.
매 loop 마다 최소 비용 노드를 방문하며 SortedSet 에서 제외시킨다.

(4) 모든 노드를 방문 할 때까지 인접 노드를 BFS 방식으로 방문하며 누적 경로를 업데이트한다.

🔑 풀이 (Kotlin)

import java.util.*
import kotlin.Comparator

enum class NodeIndex {
    source,
    destination,
    cost
}

data class NodeDistance (val nodeNumber: Int, var distance: Int = Int.MAX_VALUE)

class Delivery {

    fun solution(N: Int, road: Array<IntArray>, k: Int): Int {

        val nodeDistances = Array<NodeDistance>(N + 1){NodeDistance(it, Int.MAX_VALUE)}
        // start node number is 1
        nodeDistances[1].distance = 0


        // distance 거리 비용부터 우선순위로 오름차순
        // 거리가 같은 놈일 경우 무시할 수 없으니 index 번호 낮은 애로 선정
        // 1. make distance set
        val comparator = Comparator<NodeDistance> {
                firstNode , secondNode ->
            if (firstNode.distance != secondNode.distance) firstNode.distance - secondNode.distance
            else firstNode.nodeNumber - secondNode.nodeNumber
        }

        val distanceSet = nodeDistances.toSortedSet(comparator)
        distanceSet.remove(NodeDistance(0)) // 0번 노드는 쓰이지 않으므로 미리 삭제

        val adjacentList = Array<LinkedList<IntArray>>(N + 1){LinkedList()}

        // 2. connect edge of undirected graph
        road.forEach {
            adjacentList[it[NodeIndex.source.ordinal]].add(intArrayOf(it[NodeIndex.destination.ordinal], it[NodeIndex.cost.ordinal]))
            adjacentList[it[NodeIndex.destination.ordinal]].add(intArrayOf(it[NodeIndex.source.ordinal], it[NodeIndex.cost.ordinal]))
        }

        // 3. iterate loop until visit all nodes

        while (distanceSet.isNotEmpty()) {
            val targetNode = distanceSet.first() // pick minimum cost node
            distanceSet.remove(targetNode)

            // 4. update with iterate, when adjacent node cost is lower than before table
            for ((nextNodeNumber, cost) in adjacentList[targetNode.nodeNumber]) {
                // ignore already visited node
                if (!distanceSet.contains(NodeDistance(nextNodeNumber, nodeDistances[nextNodeNumber].distance))) continue

                if (nodeDistances[nextNodeNumber].distance > nodeDistances[targetNode.nodeNumber].distance + cost) {
                    // 한번에 set 안의 원소 업데이트가 불가능하므로 구버전을 삭제하고
                    distanceSet.remove(NodeDistance(nextNodeNumber, nodeDistances[nextNodeNumber].distance))
                    nodeDistances[nextNodeNumber].distance = nodeDistances[targetNode.nodeNumber].distance + cost // update
                    // 업데이트된 신버전 상태를 반영함.
                    distanceSet.add(NodeDistance(nextNodeNumber, nodeDistances[nextNodeNumber].distance))
                }

            }

        }

        return nodeDistances.count { it.distance <= k }
    }
}

---

Comparator

• Comparator
  Interface 로서 compare 메소드를 갖는다.
  정렬 우선순위를 커스터마이징하기 위해 쓰인다.

     val comparator = Comparator<NodeDistance> {
              firstNode , secondNode ->
          if (firstNode.distance != secondNode.distance) firstNode.distance - secondNode.distance
          else firstNode.nodeNumber - secondNode.nodeNumber
     }
     
	val distanceSet = nodeDistances.toSortedSet(comparator)

• Comparable
  Comparator의 조상 Interface 이다.

• compareBy
  Comparator를 natural order 기준으로 간단하게 생성하는 shortcut 이다.
  정렬 기준을 람다식에 명시해주기만 하면 된다.
  thenBy 메소드를 통해 첫번째 comparator가 동점처리 된 경우 2번째 3번째 우선순위를 명시해줄 수 있다.

// 완벽하게 Comparator 와 똑같이 동작한다.
// 우선 정렬순위는 distance고 distance 가 같은 항목에 대해서만 nodeNumber로 대소비교한다.
// natural order (숫자의 경우 오름차순이 기본)
val distanceSet = nodeDistances.toSortedSet(compareBy<NodeDistance>{it.distance}.thenBy{it.nodeNumber})

• compareTo
  앞놈이 뒷놈보다 작으면 -1, 같으면 0, 크면 1을 반환한다.