\n \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c \uc790\uc8fc \ub4f1\uc7a5\ud558\ub294 \ubb38\uc81c \uc911 \ud558\ub098\ub294 ‘\ucd5c\uc18c \ube44\uc6a9 \uad6c\ud558\uae30’ \ubb38\uc81c\uc785\ub2c8\ub2e4.
\n \uc774 \ubb38\uc81c\ub294 \ud2b9\uc815 \uc870\uac74\uc744 \ub9cc\uc871\uc2dc\ud0a4\uba74\uc11c \ube44\uc6a9\uc744 \ucd5c\uc18c\ud654\ud574\uc57c \ud558\ub294 \uc0c1\ud669\uc5d0\uc11c,
\n \ub2e4\uc591\ud55c \uc54c\uace0\ub9ac\uc998\uc744 \ud65c\uc6a9\ud558\uc5ec \ud6a8\uc728\uc801\uc73c\ub85c \ud574\uacb0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.
\n \uc774\ubc88 \uae00\uc5d0\uc11c\ub294 C#\uc744 \uc774\uc6a9\ud574 \ucd5c\uc18c \ube44\uc6a9 \uad6c\ud558\uae30 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ubc29\ubc95\uc744 \uc790\uc138\ud788 \uc0b4\ud3b4\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.\n <\/p>\n
\ubb38\uc81c \uc124\uba85<\/h2>\n
\n \uc8fc\uc5b4\uc9c4 \uadf8\ub798\ud504\uc5d0\uc11c \uac01 \uac04\uc120\uc740 \ud2b9\uc815 \ube44\uc6a9\uc744 \uac00\uc9c0\uace0 \uc788\uc2b5\ub2c8\ub2e4.
\n \uc2dc\uc791 \uc815\uc810\uc5d0\uc11c \ub2e4\ub978 \ubaa8\ub4e0 \uc815\uc810\uc73c\ub85c \uac00\ub294 \ucd5c\uc18c \ube44\uc6a9 \uacbd\ub85c\ub97c \ucc3e\ub294 \ubb38\uc81c\uac00 \uc8fc\uc5b4\uc84c\uc744 \ub54c,
\n \uc6b0\ub9ac\ub294 \uc774\ub97c \ud6a8\uc728\uc801\uc73c\ub85c \ud574\uacb0\ud574\uc57c \ud569\ub2c8\ub2e4.\n <\/p>\n
\ubb38\uc81c \uc815\uc758<\/h3>\n
\n \uc815\uc810\uc758 \uac1c\uc218\ub294 N, \uac04\uc120\uc758 \uac1c\uc218\ub294 M\uc774\ub77c\uace0 \uac00\uc815\ud560 \ub54c,
\n \ub2e4\uc74c\uacfc \uac19\uc740 \uc870\uac74\uc744 \ub9cc\uc871\ud558\ub294 \uadf8\ub798\ud504\uac00 \uc8fc\uc5b4\uc9c4\ub2e4\uace0 \ud569\uc2dc\ub2e4.\n <\/p>\n
- \n
- N (1 <= N <= 1000): \uc815\uc810\uc758 \uac1c\uc218<\/li>\n
- M (1 <= M <= 10000): \uac04\uc120\uc758 \uac1c\uc218<\/li>\n
- \ube44\uc6a9\uc740 1 \uc774\uc0c1 10000 \uc774\ud558\uc758 \uc815\uc218<\/li>\n<\/ul>\n
\n\uc785\ub825:<\/strong> \uc2dc\uc791 \uc815\uc810\uacfc \uac01 \uc815\uc810 \uac04\uc758 \ube44\uc6a9 \uc815\ubcf4\uac00 \uc8fc\uc5b4\uc9c4\ub2e4.
\n\ucd9c\ub825:<\/strong> \uc2dc\uc791 \uc815\uc810\uc5d0\uc11c \ub2e4\ub978 \ubaa8\ub4e0 \uc815\uc810\uc73c\ub85c \uac00\ub294 \ucd5c\uc18c \ube44\uc6a9 \uacbd\ub85c\uc758 \ubc30\uc5f4\uc744 \ucd9c\ub825\ud55c\ub2e4.\n <\/p>\n\uc608\uc2dc<\/h2>\n
\uc785\ub825<\/h3>\n
\n 5 7\n 1 2 2\n 1 3 3\n 2 3 1\n 2 4 5\n 3 4 1\n 3 5 5\n 4 5 2\n 1\n <\/pre>\n
\ucd9c\ub825<\/h3>\n
\n 0 2 3 7 5\n <\/pre>\n
\n \uc704\uc758 \uc608\uc2dc\uc5d0\uc11c \uc815\uc810 1\uc5d0\uc11c \ucd9c\ubc1c\ud588\uc744 \ub54c,
\n \uc815\uc810 2\uae4c\uc9c0\ub294 2, \uc815\uc810 3\uae4c\uc9c0\ub294 3, \uc815\uc810 4\uae4c\uc9c0\ub294 7, \uc815\uc810 5\uae4c\uc9c0\ub294 5\uc758 \ube44\uc6a9\uc774 \ud544\uc694\ud569\ub2c8\ub2e4.
\n \uac01 \ube44\uc6a9\uc774 \ucd5c\uc18c\uac00 \ub418\ub3c4\ub85d \uacbd\ub85c\ub97c \uc124\uc815\ud574\uc57c \ud569\ub2c8\ub2e4.\n <\/p>\n\uc54c\uace0\ub9ac\uc998 \uc124\uba85<\/h2>\n
\n \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574 Dijkstra \uc54c\uace0\ub9ac\uc998\uc744 \ud65c\uc6a9\ud560 \uac83\uc785\ub2c8\ub2e4.
\n Dijkstra \uc54c\uace0\ub9ac\uc998\uc740 \uac00\uc911\uce58\uac00 \uc788\ub294 \uadf8\ub798\ud504\uc5d0\uc11c \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ucc3e\ub294 \uc54c\uace0\ub9ac\uc998\uc73c\ub85c,
\n \ub2e4\uc74c\uacfc \uac19\uc740 \uc808\ucc28\ub85c \uc9c4\ud589\ub429\ub2c8\ub2e4:\n <\/p>\n- \n
- \uc2dc\uc791 \uc815\uc810\uc744 \uc124\uc815\ud558\uace0, \uc774 \uc815\uc810\uc758 \uac70\ub9ac \uac12\uc744 0\uc73c\ub85c \uc124\uc815\ud569\ub2c8\ub2e4.<\/li>\n
- \ubaa8\ub4e0 \ub2e4\ub978 \uc815\uc810\uc758 \uac70\ub9ac \uac12\uc744 \ubb34\ud55c\ub300\ub85c \ucd08\uae30\ud654\ud569\ub2c8\ub2e4.<\/li>\n
- \uac00\uc7a5 \ube44\uc6a9\uc774 \uc801\uac8c \ub4dc\ub294 \uc815\uc810\uc744 \uc120\ud0dd\ud558\uc5ec \uc8fc\ubcc0 \uc815\uc810\uc73c\ub85c\uc758 \uac70\ub9ac \uac12\uc744 \uac31\uc2e0\ud569\ub2c8\ub2e4.<\/li>\n
- \ubaa8\ub4e0 \uc815\uc810\uc5d0 \ub300\ud574 \uc704 \uacfc\uc815\uc744 \ubc18\ubcf5\ud569\ub2c8\ub2e4. \ucd5c\uc885\uc801\uc73c\ub85c \uac01 \uc815\uc810\uc5d0 \ub300\ud55c \ucd5c\uc18c \ube44\uc6a9\uc774 \uacc4\uc0b0\ub429\ub2c8\ub2e4.<\/li>\n<\/ol>\n
C# \uad6c\ud604<\/h2>\n
\n \uc774\uc81c Dijkstra \uc54c\uace0\ub9ac\uc998\uc744 C#\uc73c\ub85c \uad6c\ud604\ud574 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4.
\n \uba3c\uc800 \ud544\uc694\ud55c \ub77c\uc774\ube0c\ub7ec\ub9ac\ub97c \ucc38\uc870\ud558\uace0, \uadf8\ub798\ud504\ub97c \ud45c\ud604\ud558\uae30 \uc704\ud574 \uc778\uc811 \ub9ac\uc2a4\ud2b8\ub97c \uc0ac\uc6a9\ud558\uaca0\uc2b5\ub2c8\ub2e4.\n <\/p>\n\n using System;\n using System.Collections.Generic;\n\n class Program\n {\n static void Main(string[] args)\n {\n int n = 5; \/\/ \uc815\uc810 \uac1c\uc218\n int m = 7; \/\/ \uac04\uc120 \uac1c\uc218\n List\n {\n List elements = new List ();\n\n public int Count => elements.Count;\n\n public void Enqueue(T item)\n {\n elements.Add(item);\n var index = elements.Count - 1;\n while (index > 0)\n {\n var parentIndex = (index - 1) \/ 2;\n if (Compare(elements[index], elements[parentIndex]) >= 0) break;\n Swap(index, parentIndex);\n index = parentIndex;\n }\n }\n\n public T Dequeue()\n {\n var lastIndex = elements.Count - 1;\n var firstElement = elements[0];\n elements[0] = elements[lastIndex];\n elements.RemoveAt(lastIndex);\n\n --lastIndex;\n\n int index = 0;\n while (true)\n {\n var leftChildIndex = index * 2 + 1;\n var rightChildIndex = index * 2 + 2;\n int smallestChildIndex;\n\n if (leftChildIndex > lastIndex) break;\n if (rightChildIndex > lastIndex) smallestChildIndex = leftChildIndex;\n else smallestChildIndex = Compare(elements[leftChildIndex], elements[rightChildIndex]) < 0 ? leftChildIndex : rightChildIndex;\n\n if (Compare(elements[index], elements[smallestChildIndex]) <= 0) break;\n\n Swap(index, smallestChildIndex);\n index = smallestChildIndex;\n }\n\n return firstElement;\n }\n\n void Swap(int indexA, int indexB)\n {\n var temp = elements[indexA];\n elements[indexA] = elements[indexB];\n elements[indexB] = temp;\n }\n\n int Compare(T a, T b)\n {\n \/\/ \uc0ac\uc6a9\uc790 \uc815\uc758 \ube44\uad50 \ub85c\uc9c1 \uc5ec\uae30\uc5d0 \uad6c\ud604 \ud544\uc694\n \/\/ \uc608\ub97c \ub4e4\uc5b4, Tuple \uc54c\uace0\ub9ac\uc998 \ubd84\uc11d<\/h2>\n
\n \uc704\uc758 \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud558\uba74 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O((N + M) log N)\uc785\ub2c8\ub2e4.
\n \uc5ec\uae30\uc11c N\uc740 \uc815\uc810\uc758 \uc218, M\uc740 \uac04\uc120\uc758 \uc218\uc785\ub2c8\ub2e4.
\n Dijkstra \uc54c\uace0\ub9ac\uc998\uc740 \uc77c\ubc18\uc801\uc73c\ub85c \ube44\ud6a8\uc728\uc801\uc774\uc9c0 \uc54a\uc73c\uba70,
\n \ub9ce\uc740 \uacbd\uc6b0\uc5d0 \ucd5c\uc18c \ube44\uc6a9\uc744 \uad6c\ud558\ub294 \ub370 \ud6a8\uacfc\uc801\uc785\ub2c8\ub2e4.
\n \ub2e8, \ubaa8\ub4e0 \uac04\uc120\uc758 \uac00\uc911\uce58\uac00 \uc74c\uc218\uac00 \uc544\ub2c8\uc5b4\uc57c \ud55c\ub2e4\ub294 \uc810\uc744 \uc720\uc758\ud574\uc57c \ud569\ub2c8\ub2e4.\n <\/p>\n\uacb0\ub860<\/h2>\n
\n \uc774\ubc88 \uac15\uc88c\uc5d0\uc11c\ub294 C#\uc744 \ud1b5\ud574 \ucd5c\uc18c \ube44\uc6a9 \uad6c\ud558\uae30 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud55c Dijkstra \uc54c\uace0\ub9ac\uc998\uc744
\n \uc0b4\ud3b4\ubcf4\uc558\uc2b5\ub2c8\ub2e4. \ubb38\uc81c\ub97c \uc815\uc758\ud558\uace0, \uc54c\uace0\ub9ac\uc998\uc744 \uc124\uba85\ud55c \ud6c4
\n \uc2e4\uc81c \ucf54\ub4dc\ub97c \uad6c\ud604\ud558\ub294 \uacfc\uc815\uc744 \ucc28\uadfc\ucc28\uadfc \uc9c4\ud589\ud588\uc2b5\ub2c8\ub2e4.
\n \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c \uc774\ub7ec\ud55c \ubb38\uc81c\ub4e4\uc774 \uc790\uc8fc \ucd9c\uc81c\ub418\ubbc0\ub85c, \ucda9\ubd84\ud788 \uc5f0\uc2b5\ud558\uace0 \uc774\ud574\ud558\ub294 \uac83\uc774 \uc911\uc694\ud569\ub2c8\ub2e4.
\n \uc774\ubc88 \uae00\uc774 \ucf54\ub529 \ud14c\uc2a4\ud2b8 \uc900\ube44\uc5d0 \ub3c4\uc6c0\uc774 \ub418\uae38 \ubc14\ub78d\ub2c8\ub2e4.\n <\/p>\n<\/article>\n<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"