配達する

🔒 質問する

🧠 構想

グラフィックの1ノードから開始
全ての頂点の最短経路を求め、基準距離値K以下のノードが送達可能範囲に属する
=>すべての頂点への最短パス=Dijkstra

ダエストラ

(1)すべての頂点のパス料金表を生成する.
🟥 この問題では、0番ノードがないと仮定します.始点は「1」番ノードに固定され、配列のインデックスは始点ノード番号になります.
🟥 1を除いて,すべてのノードのパス料金は無限に初期化される.
(2)ノードを接続する.인접 리스트(adjacentList)を使用して、各ノードの接続ノードを管理します.
ループの無方向図を許可するため、双方向に接続されます.
(3)SortedSet資料構造を用いて最短パスノードからアクセスを開始する.
各ループは最小コストノードにアクセスし、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
インタフェースとして、比較方法を使用します.
ソートの優先順位をカスタマイズします.

     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)

ComparableComparatorの祖先インタフェース.

compareBy
これはComparatorを自然秩序基準として簡単に生成される近道である.
青茶の儀式に並べ替え基準を明記すればいい.thenByの方法により、第1のcomparator処理が同分である場合、第2の第3の優先度を指定することができる.

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

compareTo
前は後より1小さく、0に等しく、大きいのは1を返します.