\uc548\ub155\ud558\uc138\uc694, \uc5ec\ub7ec\ubd84! \uc624\ub298\uc740 \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998<\/strong>\uc5d0 \ub300\ud574 \uae4a\uc774 \uc788\uac8c \uc54c\uc544\ubcf4\uace0, \uc2e4\uc81c \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c \uc790\uc8fc \ucd9c\uc81c\ub418\ub294 \ubb38\uc81c\ub97c \ud480\uc5b4\ubcf4\ub3c4\ub85d \ud558\uaca0\uc2b5\ub2c8\ub2e4. \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\uc740 \uac00\uc911\uce58\uac00 \uc788\ub294 \ubbf8\uadf8\ub798\ud504\uc5d0\uc11c \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ucc3e\ub294 \uc54c\uace0\ub9ac\uc998\uc73c\ub85c, \uc8fc\ub85c \ub124\ud2b8\uc6cc\ud06c \ucd5c\ub2e8 \uacbd\ub85c \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ub370 \uc0ac\uc6a9\ub429\ub2c8\ub2e4.<\/p>\n \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\uc740 1956\ub144 \uc5d0\ub4dc\uac00 \ub2e4\uc775\uc2a4\ud2b8\ub77c\uc5d0 \uc758\ud574 \uac1c\ubc1c\ub41c \ucd5c\ub2e8 \uacbd\ub85c \uc54c\uace0\ub9ac\uc998\uc73c\ub85c, \ud2b9\uc815 \uc815\uc810\uc5d0\uc11c \uc2dc\uc791\ud558\uc5ec \ub2e4\ub978 \ubaa8\ub4e0 \uc815\uc810\uc73c\ub85c \uac00\ub294 \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ucc3e\ub294 \ub370 \uc0ac\uc6a9\ub429\ub2c8\ub2e4. \uc774 \uc54c\uace0\ub9ac\uc998\uc740 \uc74c\uc218 \uac00\uc911\uce58\ub97c \ud5c8\uc6a9\ud558\uc9c0 \uc54a\uc73c\uba70, \uadf8\ub798\ud504\uac00 \uc5f0\uacb0\ub418\uc5b4 \uc788\ub2e4\uace0 \uac00\uc815\ud569\ub2c8\ub2e4.<\/p>\n \uc774\uc81c \uc2e4\uc81c \ubb38\uc81c\ub97c \ud1b5\ud574 \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\uc744 \uc801\uc6a9\ud574\ubd05\uc2dc\ub2e4.<\/p>\n \uc785\ub825\uc73c\ub85c \uc8fc\uc5b4\uc9c4 \uadf8\ub798\ud504\uac00 \uc8fc\uc5b4\uc84c\uc744 \ub54c, \ud2b9\uc815 \uc2dc\uc791 \uc815\uc810\uc5d0\uc11c \ubaa8\ub4e0 \ub2e4\ub978 \uc815\uc810\uae4c\uc9c0\uc758 \ucd5c\ub2e8 \uacbd\ub85c\ub97c \uad6c\ud558\ub294 \ud504\ub85c\uadf8\ub7a8\uc744 \uc791\uc131\ud558\uc2dc\uc624.<\/p>\n \uc2dc\uc791 \uc815\uc810 \uc6b0\uc120 \uc8fc\uc5b4\uc9c4 \uac04\uc120 \uc815\ubcf4\ub97c \ubc14\ud0d5\uc73c\ub85c \uadf8\ub798\ud504\ub97c \uc778\uc811 \ub9ac\uc2a4\ud2b8<\/strong>\ub85c \ud45c\ud604\ud569\ub2c8\ub2e4. \ud30c\uc774\uc36c\uc5d0\uc11c\ub294 \ub515\uc154\ub108\ub9ac(Dictionary)\ub97c \uc0ac\uc6a9\ud558\uc5ec \uac01 \uc815\uc810\uacfc \uadf8 \uc815\uc810\uacfc \uc5f0\uacb0\ub41c \ub2e4\ub978 \uc815\uc810 \ubc0f \uac00\uc911\uce58\ub97c \uc800\uc7a5\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n \uc774\uc81c \uc2e4\uc81c \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\uc744 \uad6c\ud604\ud569\ub2c8\ub2e4. \uc774 \uc54c\uace0\ub9ac\uc998\uc740 \uc6b0\uc120\uc21c\uc704 \ud050\ub97c \ud65c\uc6a9\ud558\uc5ec \ud604\uc7ac\uae4c\uc9c0\uc758 \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ud6a8\uc728\uc801\uc73c\ub85c \uc5c5\ub370\uc774\ud2b8\ud569\ub2c8\ub2e4.<\/p>\n \ubaa8\ub4e0 \uc694\uc18c\ub97c \uc885\ud569\ud558\uc5ec \ucd5c\uc885\uc801\uc778 \ucf54\ub4dc\ub97c \uc791\uc131\ud569\ub2c8\ub2e4. \uc785\ub825\uc744 \ubc1b\uace0 \uacb0\uacfc\ub97c \ucc98\ub9ac\ud558\ub294 \ubd80\ubd84\ub3c4 \ud3ec\ud568\ub418\uc5b4 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 \uc0ac\uc6a9\ub41c \ub370\uc774\ud130 \uad6c\uc870\uc5d0 \ub530\ub77c \ub2ec\ub77c\uc9d1\ub2c8\ub2e4. \uc77c\ubc18\uc801\uc73c\ub85c \uc6b0\uc120\uc21c\uc704 \ud050\ub97c \uc0ac\uc6a9\ud560 \uacbd\uc6b0 O((V + E) log V)\uc785\ub2c8\ub2e4. \uc5ec\uae30\uc11c \uc774\ubc88 \uac15\uc88c\uc5d0\uc11c \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\uc744 \ud1b5\ud574 \ucd5c\ub2e8 \uacbd\ub85c \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ubc29\ubc95\uc744 \ubc30\uc6b0\uace0, \uc2e4\uc81c \uc785\ub825\uc744 \ub2e4\ub8e8\uc5b4 \ubcf4\uc558\uc2b5\ub2c8\ub2e4. \uc774 \uc54c\uace0\ub9ac\uc998\uc740 \ub124\ud2b8\uc6cc\ud06c, \uac8c\uc784 \uac1c\ubc1c \ub4f1 \ub2e4\uc591\ud55c \ubd84\uc57c\uc5d0\uc11c \ud65c\uc6a9\ub420 \uc218 \uc788\uc73c\ubbc0\ub85c, \uc798 \uc219\uc9c0\ud574\ub450\uba74 \uc88b\uc2b5\ub2c8\ub2e4.<\/p>\n \ucd94\uac00 \ubb38\uc81c\ub97c \ud1b5\ud574 \ub354 \ub2e4\uc591\ud55c \uc0c1\ud669\uc744 \uc5f0\uc2b5\ud574 \ubcf4\uc2dc\uae30 \ubc14\ub78d\ub2c8\ub2e4. \ub2e4\uc74c \uac15\uc88c\uc5d0\uc11c\ub294 \ub2e4\ub978 \uc54c\uace0\ub9ac\uc998\uc744 \uc0b4\ud3b4\ubcf4\ub3c4\ub85d \ud558\uaca0\uc2b5\ub2c8\ub2e4. \uac10\uc0ac\ud569\ub2c8\ub2e4!<\/p>\n <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"1. \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998 \uac1c\uc694<\/h2>\n
1.1 \uc54c\uace0\ub9ac\uc998 \ub3d9\uc791 \uc6d0\ub9ac<\/h3>\n
\n
2. \ubb38\uc81c \uc124\uba85<\/h2>\n
\ubb38\uc81c: \ucd5c\ub2e8 \uacbd\ub85c \ucc3e\uae30<\/h3>\n
\uc785\ub825 \uc870\uac74<\/h4>\n
\n
V<\/code>\uc640 \uac04\uc120\uc758 \uac1c\uc218 E<\/code>\uac00 \uc8fc\uc5b4\uc9c4\ub2e4. (1 \u2264 V \u2264 20, 1 \u2264 E \u2264 100)<\/li>\nA<\/code>, \ub3c4\ucc29 \uc815\uc810 B<\/code>, \uac00\uc911\uce58 C<\/code> \ud615\ud0dc\ub85c \uc8fc\uc5b4\uc9c4\ub2e4.<\/li>\nK<\/code>\uac00 \uc8fc\uc5b4\uc9c4\ub2e4.<\/li>\n<\/ul>\n\ucd9c\ub825 \uc870\uac74<\/h4>\n
K<\/code>\uc5d0\uc11c \ub2e4\ub978 \ubaa8\ub4e0 \uc815\uc810\uae4c\uc9c0\uc758 \ucd5c\ub2e8 \uac70\ub9ac\ub97c \ucd9c\ub825\ud569\ub2c8\ub2e4. \ub9cc\uc57d \uc5b4\ub5a4 \uc815\uc810\uae4c\uc9c0\uc758 \uacbd\ub85c\uac00 \uc5c6\ub2e4\uba74 INF<\/code>\ub97c \ucd9c\ub825\ud569\ub2c8\ub2e4.<\/p>\n3. \ubb38\uc81c \ud480\uc774 \uacfc\uc815<\/h2>\n
3.1 \uadf8\ub798\ud504 \ud45c\ud604<\/h3>\n
from collections import defaultdict\nimport heapq\n\ndef create_graph(edges):\n graph = defaultdict(list)\n for A, B, C in edges:\n graph[A].append((B, C))\n return graph\n<\/code><\/pre>\n3.2 \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998 \uad6c\ud604<\/h3>\n
def dijkstra(graph, start, V):\n distances = {vertex: float('inf') for vertex in range(1, V + 1)}\n distances[start] = 0\n priority_queue = [(0, start)]\n\n while priority_queue:\n current_distance, current_vertex = heapq.heappop(priority_queue)\n\n if current_distance > distances[current_vertex]:\n continue\n\n for neighbor, weight in graph[current_vertex]:\n distance = current_distance + weight\n\n if distance < distances[neighbor]:\n distances[neighbor] = distance\n heapq.heappush(priority_queue, (distance, neighbor))\n\n return distances\n<\/code><\/pre>\n3.3 \ucd5c\uc885 \ucf54\ub4dc<\/h3>\n
def main():\n V, E = map(int, input().split())\n edges = [tuple(map(int, input().split())) for _ in range(E)]\n K = int(input())\n\n graph = create_graph(edges)\n distances = dijkstra(graph, K, V)\n\n for vertex in range(1, V + 1):\n if distances[vertex] == float('inf'):\n print(\"INF\")\n else:\n print(distances[vertex])\n\nif __name__ == \"__main__\":\n main()\n<\/code><\/pre>\n4. \uc2dc\uac04 \ubcf5\uc7a1\ub3c4<\/h2>\n
V<\/code>\ub294 \uc815\uc810\uc758 \uc218, E<\/code>\ub294 \uac04\uc120\uc758 \uc218\uc785\ub2c8\ub2e4.<\/p>\n5. \uacb0\ub860<\/h2>\n