\uc774 \uac15\uc88c\uc5d0\uc11c\ub294 \uc790\ubc14\uc2a4\ud06c\ub9bd\ud2b8\ub97c \ud65c\uc6a9\ud558\uc5ec K\ubc88\uc9f8 \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ucc3e\ub294 \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ub97c \ub2e4\ub8e8\uc5b4 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uc774 \ubb38\uc81c\ub294 \uadf8\ub798\ud504 \uc774\ub860\uacfc \uacbd\ub85c \ucc3e\uae30 \uc54c\uace0\ub9ac\uc998\uc758 \ud0c4\ud0c4\ud55c \uc774\ud574\ub97c \uc694\uad6c\ud558\uba70, \ud6a8\uc728\uc801\uc778 \ucf54\ub4dc\ub97c \uc791\uc131\ud558\ub294 \ub370 \ucd08\uc810\uc744 \ub9de\ucd94\uace0 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n
\uae30\ubcf8\uc801\uc73c\ub85c \uc8fc\uc5b4\uc9c4 \uadf8\ub798\ud504\uc5d0\uc11c \ud55c \uc815\uc810\uc5d0\uc11c \ub2e4\ub978 \uc815\uc810\uc73c\ub85c \uac00\ub294 \ubaa8\ub4e0 \uac00\ub2a5\ud55c \uacbd\ub85c \uc911\uc5d0\uc11c K\ubc88\uc9f8\ub85c \uc9e7\uc740 \uacbd\ub85c\uc758 \ucd1d \uae38\uc774\ub97c \ucc3e\uc544\uc57c \ud569\ub2c8\ub2e4.<\/p>\n
K\ubc88\uc9f8\ub85c \uc9e7\uc740 \uacbd\ub85c\uc758 \ucd1d \uae38\uc774\ub97c \ucd9c\ub825\ud569\ub2c8\ub2e4. \ub9cc\uc57d K\ubc88\uc9f8\ub85c \uc9e7\uc740 \uacbd\ub85c\uac00 \uc874\uc7ac\ud558\uc9c0 \uc54a\uc744 \uacbd\uc6b0\uc5d0\ub294 -1\uc744 \ucd9c\ub825\ud574\uc57c \ud569\ub2c8\ub2e4.<\/p>\n
\n 4 5 2\n 1 2 4\n 1 3 2\n 3 2 5\n 2 4 1\n 3 4 3\n <\/pre>\n\ucd9c\ub825 \uc608\uc2dc<\/h3>\n
\n 5\n <\/pre>\n<\/div>\n\ubb38\uc81c \ud574\uacb0 \uc811\uadfc\ubc95<\/h2>\n
K\ubc88\uc9f8 \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ucc3e\uae30 \uc704\ud574 \uc5ec\ub7ec\uac00\uc9c0 \ubc29\ubc95 \uc911, \ucd5c\uc801\uc758 \uc54c\uace0\ub9ac\uc998\uc740 \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\uc744 \uc218\uc815\ud558\uc5ec \uc0ac\uc6a9\ud558\ub294 \uac83\uc785\ub2c8\ub2e4. \uae30\ubcf8\uc801\uc73c\ub85c \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\uc740 \uac00\uc7a5 \uc9e7\uc740 \uacbd\ub85c\ub97c \ucc3e\ub294 \ub370\uc5d0 \uc0ac\uc6a9\ub418\uc9c0\ub9cc, K\ubc88\uc9f8 \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ucc3e\uae30 \uc704\ud574\uc11c\ub294 \uacbd\ub85c\ub97c \uc5ec\ub7ec \ubc88 \ud0d0\uc0c9\ud560 \uc218 \uc788\ub3c4\ub85d \ud574\uc57c \ud569\ub2c8\ub2e4.<\/p>\n
\ub2e8\uacc4\ubcc4 \ud480\uc774 \uacfc\uc815<\/h3>\n
1. \uadf8\ub798\ud504 \ud45c\ud604<\/h4>\n
\uadf8\ub798\ud504\ub294 \uc778\uc811 \ub9ac\uc2a4\ud2b8 \ud615\ud0dc\ub85c \ud45c\ud604\ud558\uba70, \uac01 \ub178\ub4dc\uc5d0\ub294 \uc5f0\uacb0\ub41c \ub178\ub4dc\uc640 \uadf8 \uacbd\ub85c\uc758 \uac00\uc911\uce58 \uc815\ubcf4\ub97c \uc800\uc7a5\ud569\ub2c8\ub2e4. \uc774\ub97c \ud1b5\ud574 \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\uc744 \ud6a8\uc728\uc801\uc73c\ub85c \uc801\uc6a9\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n
2. \uc6b0\uc120\uc21c\uc704 \ud050 \uc0ac\uc6a9<\/h4>\n
Javscript\uc758
PriorityQueue<\/code>\ub97c \ud65c\uc6a9\ud558\uc5ec \uac00\uc7a5 \uc9e7\uc740 \uacbd\ub85c\ub97c \uc6b0\uc120\uc801\uc73c\ub85c \ud0d0\uc0c9\ud569\ub2c8\ub2e4. \uac01 \uacbd\ub85c\uc758 \uc815\ubcf4\ub97c \ub2f4\uace0 \uc788\uc5b4, \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\ucc98\ub7fc \ucd5c\uc18c \ube44\uc6a9\ubd80\ud130 \ud0d0\uc0c9\ud560 \uc218 \uc788\ub3c4\ub85d \uc124\uc815\ud569\ub2c8\ub2e4.<\/p>\n3. K\ubc88\uc9f8 \uacbd\ub85c \ud0d0\uc0c9<\/h4>\n
\uacbd\ub85c\ub97c \ud0d0\uc0c9\ud558\uba70, K\ubc88\uc9f8\ub85c \uc9e7\uc740 \uacbd\ub85c\ub97c \ucc3e\uae30 \uc704\ud55c \uce74\uc6b4\ud2b8\ub97c \uc720\uc9c0\ud569\ub2c8\ub2e4. \uacbd\ub85c\uc758 \uae38\uc774\ub97c \ubc30\uc5f4\uc5d0 \uc800\uc7a5\ud558\uba70, K\ubc88\uc9f8\ub85c \ub3c4\ub2ec\ud55c \uacbd\uc6b0 \ud574\ub2f9 \uae38\uc774\ub97c \ubc18\ud658\ud558\uace0, \uadf8\ub807\uc9c0 \uc54a\uc73c\uba74 \uacc4\uc18d \ud0d0\uc0c9\ud569\ub2c8\ub2e4.<\/p>\n
4. \uacb0\uacfc \ucd9c\ub825<\/h4>\n
\ubaa8\ub4e0 \uacbd\ub85c\ub97c \ud0d0\uc0c9\ud55c \ub4a4, K\ubc88\uc9f8 \uacbd\ub85c\uac00 \uc5c6\uc744 \uacbd\uc6b0 -1\uc744 \ucd9c\ub825\ud569\ub2c8\ub2e4.<\/p>\n
\uad6c\ud604 \ucf54\ub4dc<\/h2>\n
\uc544\ub798\uc758 \ucf54\ub4dc\ub294 \uc704\uc758 \uc124\uba85\uc744 \uae30\ubc18\uc73c\ub85c K\ubc88\uc9f8 \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ucc3e\ub294 \uc790\ubc14\uc2a4\ud06c\ub9bd\ud2b8 \ubc84\uc804\uc785\ub2c8\ub2e4.<\/p>\n
\nclass MinHeap {\n constructor() {\n this.heap = [];\n }\n\n insert(node) {\n this.heap.push(node);\n this.bubbleUp();\n }\n\n bubbleUp() {\n let index = this.heap.length - 1;\n const element = this.heap[index];\n\n while (index > 0) {\n let parentIndex = Math.floor((index - 1) \/ 2);\n let parent = this.heap[parentIndex];\n\n if (element[1] >= parent[1]) break;\n\n this.heap[index] = parent;\n index = parentIndex;\n }\n this.heap[index] = element;\n }\n\n extractMin() {\n const min = this.heap[0];\n const end = this.heap.pop();\n if (this.heap.length > 0) {\n this.heap[0] = end;\n this.sinkDown();\n }\n return min;\n }\n\n sinkDown() {\n let index = 0;\n const length = this.heap.length;\n const element = this.heap[0];\n\n while (true) {\n let leftChildIndex = 2 * index + 1;\n let rightChildIndex = 2 * index + 2;\n let leftChild, rightChild;\n let swap = null;\n\n if (leftChildIndex < length) {\n leftChild = this.heap[leftChildIndex];\n if (leftChild[1] < element[1]) {\n swap = leftChildIndex;\n }\n }\n\n if (rightChildIndex < length) {\n rightChild = this.heap[rightChildIndex];\n if ((swap === null && rightChild[1] < element[1]) || \n (swap !== null && rightChild[1] < leftChild[1])) {\n swap = rightChildIndex;\n }\n }\n\n if (swap === null) break;\n\n this.heap[index] = this.heap[swap];\n index = swap;\n }\n this.heap[index] = element;\n }\n}\n\nfunction kthShortestPath(n, edges, k) {\n const graph = Array.from({ length: n + 1 }, () => []);\n edges.forEach(([u, v, w]) => {\n graph[u].push([v, w]);\n });\n\n const minHeap = new MinHeap();\n const paths = Array.from({ length: n + 1 }, () => []);\n\n minHeap.insert([1, 0]);\n paths[1].push(0);\n\n while (minHeap.heap.length > 0) {\n const [node, distance] = minHeap.extractMin();\n\n if (paths[node].length === k) continue;\n\n for (const [neighbor, weight] of graph[node]) {\n const newDistance = distance + weight;\n\n if (paths[neighbor].length < k) {\n paths[neighbor].push(newDistance);\n paths[neighbor].sort((a, b) => a - b);\n minHeap.insert([neighbor, newDistance]);\n } else if (newDistance < paths[neighbor][paths[neighbor].length - 1]) {\n paths[neighbor][paths[neighbor].length - 1] = newDistance;\n paths[neighbor].sort((a, b) => a - b);\n minHeap.insert([neighbor, newDistance]);\n }\n }\n }\n\n return paths[n][k - 1] || -1;\n}\n\n\/\/ \uc0ac\uc6a9 \uc608\uc2dc\nconst n = 4;\nconst edges = [\n [1, 2, 4],\n [1, 3, 2],\n [3, 2, 5],\n [2, 4, 1],\n [3, 4, 3],\n];\nconst k = 2;\n\nconsole.log(kthShortestPath(n, edges, k)); \/\/ \ucd9c\ub825: 5\n<\/code><\/pre>\n\uacb0\ub860<\/h2>\n
\uc774\ubc88 \uac15\uc88c\uc5d0\uc11c\ub294 K\ubc88\uc9f8 \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ucc3e\ub294 \uc54c\uace0\ub9ac\uc998\uc5d0 \ub300\ud574 \ub2e4\ub8e8\uc5c8\uc2b5\ub2c8\ub2e4. \ucd5c\ub2e8 \uacbd\ub85c \uc54c\uace0\ub9ac\uc998\uc744 \uae30\ubc18\uc73c\ub85c \ud558\uc5ec \ubb38\uc81c\ub97c \ud574\uacb0\ud560 \uc218 \uc788\ub294 \uae30\ubc95\uc744 \uc775\ud614\uc2b5\ub2c8\ub2e4. \uc774\ub7ec\ud55c \uae30\ucd08\ub97c \ubc14\ud0d5\uc73c\ub85c \ub354 \ubcf5\uc7a1\ud55c \uadf8\ub798\ud504 \ubb38\uc81c\ub97c \ud574\uacb0\ud560 \uc218 \uc788\ub294 \ub2a5\ub825\uc744 \ud0a4\uc6b8 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n