\ucd5c\uc18c \uc2e0\uc7a5 \ud2b8\ub9ac(Minimum Spanning Tree, MST)\ub294 \uac00\uc911\uce58\uac00 \ud560\ub2f9\ub41c \ubb34\ubc29\ud5a5 \uadf8\ub798\ud504\uc5d0\uc11c \ubaa8\ub4e0 \uc815\uc810\uc744 \ud3ec\ud568\ud558\uba74\uc11c \uc804\uccb4 \uac00\uc911\uce58\uc758 \ud569\uc774 \ucd5c\uc18c\uac00 \ub418\ub294 \ud2b8\ub9ac\ub97c \ub9d0\ud569\ub2c8\ub2e4. \ucd5c\uc18c \uc2e0\uc7a5 \ud2b8\ub9ac\ub294 \ub124\ud2b8\uc6cc\ud06c \uc124\uacc4, \ud074\ub7ec\uc2a4\ud130\ub9c1 \ubc0f \uc5ec\ub7ec \ucd5c\uc801\ud654 \ubb38\uc81c\uc5d0 \uc0ac\uc6a9\ub429\ub2c8\ub2e4.<\/p>\n
\ucd5c\uc18c \uc2e0\uc7a5 \ud2b8\ub9ac\ub97c \ucc3e\uae30 \uc704\ud55c \ub300\ud45c\uc801\uc778 \uc54c\uace0\ub9ac\uc998\uc73c\ub85c\ub294 \ud06c\ub8e8\uc2a4\uce7c \uc54c\uace0\ub9ac\uc998(Kruskal’s Algorithm)\uacfc \ud504\ub9bc \uc54c\uace0\ub9ac\uc998(Prim’s Algorithm)\uc774 \uc788\uc2b5\ub2c8\ub2e4. \uc774 \ub450 \uac00\uc9c0 \uc54c\uace0\ub9ac\uc998\uc740 \uac01\uac01 \ub2e4\ub978 \ubc29\uc2dd\uc73c\ub85c MST\ub97c \uad6c\uc131\ud569\ub2c8\ub2e4.<\/p>\n
\ud06c\ub8e8\uc2a4\uce7c \uc54c\uace0\ub9ac\uc998\uc740 \uadf8\ub798\ud504\uc758 \uac04\uc120\uc744 \uac00\uc911\uce58\uc5d0 \ub530\ub77c \uc624\ub984\ucc28\uc21c\uc73c\ub85c \uc815\ub82c\ud55c \ud6c4, \uc0ac\uc774\ud074\uc744 \ud615\uc131\ud558\uc9c0 \uc54a\ub3c4\ub85d \uac04\uc120\uc744 \ucd94\uac00\ud558\uc5ec MST\ub97c \uad6c\uc131\ud558\ub294 \ubc29\uc2dd\uc785\ub2c8\ub2e4.<\/p>\n
\ud504\ub9bc \uc54c\uace0\ub9ac\uc998\uc740 \uc2dc\uc791 \uc815\uc810\uc5d0\uc11c \ucd9c\ubc1c\ud558\uc5ec \ud604\uc7ac \uc5f0\uacb0\ub41c \uc815\uc810 \uc911 \uac00\uc7a5 \uac00\uc911\uce58\uac00 \ub0ae\uc740 \uac04\uc120\uc744 \uc120\ud0dd\ud558\uc5ec MST\ub97c \ud655\uc7a5\ud574 \ub098\uac00\ub294 \ubc29\uc2dd\uc785\ub2c8\ub2e4.<\/p>\n
\ub450 \uac00\uc9c0 \uc54c\uace0\ub9ac\uc998 \ubaa8\ub450 \ud6a8\uc728\uc801\uc73c\ub85c MST\ub97c \ucc3e\uc744 \uc218 \uc788\uc9c0\ub9cc, \ud06c\ub8e8\uc2a4\uce7c\uc740 \uac04\uc120\uc758 \uc218\uac00 \uc801\uc740 \ud76c\uc18c \uadf8\ub798\ud504\uc5d0 \ub354 \uc801\ud569\ud558\uace0, \ud504\ub9bc\uc740 \uc815\uc810\uc758 \uc218\uac00 \uc801\uc740 \ubc00\uc811 \uadf8\ub798\ud504\uc5d0 \uc801\ud569\ud569\ub2c8\ub2e4.<\/p>\n
\uac00\uc911\uce58\uac00 \uc788\ub294 \ubb34\ubc29\ud5a5 \uadf8\ub798\ud504\uac00 \uc8fc\uc5b4\uc9c8 \ub54c, \ucd5c\uc18c \uc2e0\uc7a5 \ud2b8\ub9ac\ub97c \uad6c\ud558\uc2dc\uc624. \uc785\ub825\uc740 \ub2e4\uc74c\uacfc \uac19\uc740 \ud615\uc2dd\uc785\ub2c8\ub2e4:<\/p>\n
V<\/code>\uc640 \uac04\uc120\uc758 \uc218 E<\/code>\uac00 \uc8fc\uc5b4\uc9c4\ub2e4.<\/li>\n- \ub2e4\uc74c
E<\/code>\uac1c\uc758 \uc904\uc5d0 \uac01\uac01 u<\/code>, v<\/code>, w<\/code>\uac00 \uc8fc\uc5b4\uc838, \uc774\ub294 \uc815\uc810 u<\/code>\uc640 v<\/code>\ub97c \uc5f0\uacb0\ud558\ub294 \uac00\uc911\uce58 w<\/code>\uc758 \uac04\uc120\uc744 \uc758\ubbf8\ud55c\ub2e4.<\/li>\n<\/ul>\n\ucd9c\ub825\uc73c\ub85c \ucd5c\uc18c \uc2e0\uc7a5 \ud2b8\ub9ac\uc758 \uac00\uc911\uce58 \ud569\uc744 \ucd9c\ub825\ud558\uc2dc\uc624.<\/p>\n
4. \ubb38\uc81c \ud480\uc774 \uc811\uadfc\ubc95<\/h2>\n
\ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574 \ub2e4\uc74c \ub2e8\uacc4\ub97c \ub530\ub985\ub2c8\ub2e4:<\/p>\n
\n- \uc785\ub825\uac12\uc744 \uc77d\uc5b4\ub4e4\uc778\ub2e4.<\/li>\n
- \uac04\uc120\uc744 \uac00\uc911\uce58\uc5d0 \ub530\ub77c \uc815\ub82c\ud55c\ub2e4.<\/li>\n
- \uc720\ub2c8\uc628-\ud30c\uc778\ub4dc(Union-Find) \uc790\ub8cc\uad6c\uc870\ub97c \uc0ac\uc6a9\ud558\uc5ec \uc0ac\uc774\ud074\uc744 \uac80\ucd9c\ud55c\ub2e4.<\/li>\n
- \uc0ac\uc774\ud074\uc774 \ud615\uc131\ub418\uc9c0 \uc54a\ub294 \uac04\uc120\uc744 MST\uc5d0 \ucd94\uac00\ud55c\ub2e4.<\/li>\n
- MST\uc758 \uac00\uc911\uce58 \ud569\uc744 \uacc4\uc0b0\ud558\uc5ec \ucd9c\ub825\ud55c\ub2e4.<\/li>\n<\/ol>\n
5. \uc790\ubc14 \ucf54\ub4dc \uad6c\ud604<\/h2>\n5.1. \uc720\ub2c8\uc628-\ud30c\uc778\ub4dc \uc790\ub8cc\uad6c\uc870 \uad6c\ud604<\/h3>\n\nclass UnionFind {\n private int[] parent;\n private int[] rank;\n\n public UnionFind(int size) {\n parent = new int[size];\n rank = new int[size];\n for (int i = 0; i < size; i++) {\n parent[i] = i;\n rank[i] = 0;\n }\n }\n\n public int find(int p) {\n if (parent[p] != p) {\n parent[p] = find(parent[p]);\n }\n return parent[p];\n }\n\n public void union(int p, int q) {\n int rootP = find(p);\n int rootQ = find(q);\n if (rootP != rootQ) {\n if (rank[rootP] > rank[rootQ]) {\n parent[rootQ] = rootP;\n } else if (rank[rootP] < rank[rootQ]) {\n parent[rootP] = rootQ;\n } else {\n parent[rootQ] = rootP;\n rank[rootP]++;\n }\n }\n }\n}\n <\/pre>\n5.2. \ud06c\ub8e8\uc2a4\uce7c \uc54c\uace0\ub9ac\uc998 \uad6c\ud604<\/h3>\n\nimport java.util.*;\n\nclass Edge implements Comparable {\n int u, v, weight;\n\n public Edge(int u, int v, int weight) {\n this.u = u;\n this.v = v;\n this.weight = weight;\n }\n\n @Override\n public int compareTo(Edge other) {\n return Integer.compare(this.weight, other.weight);\n }\n}\n\npublic class MinimumSpanningTree {\n public static void main(String[] args) {\n Scanner scanner = new Scanner(System.in);\n int V = scanner.nextInt();\n int E = scanner.nextInt();\n\n PriorityQueue edgeList = new PriorityQueue<>();\n for (int i = 0; i < E; i++) {\n int u = scanner.nextInt();\n int v = scanner.nextInt();\n int weight = scanner.nextInt();\n edgeList.add(new Edge(u, v, weight));\n }\n\n UnionFind uf = new UnionFind(V);\n int totalWeight = 0;\n\n while (!edgeList.isEmpty()) {\n Edge edge = edgeList.poll();\n if (uf.find(edge.u) != uf.find(edge.v)) {\n uf.union(edge.u, edge.v);\n totalWeight += edge.weight;\n }\n }\n\n System.out.println(totalWeight);\n }\n}\n <\/edge><\/edge><\/pre>\n6. \ucf54\ub4dc \uc124\uba85<\/h2>\n
\uc704\uc758 \ucf54\ub4dc\ub294 \ud06c\ub8e8\uc2a4\uce7c \uc54c\uace0\ub9ac\uc998\uc744 \uad6c\ud604\ud55c \uac83\uc785\ub2c8\ub2e4. \uba3c\uc800, \uc785\ub825\uc73c\ub85c \uc815\uc810\uc758 \uc218\uc640 \uac04\uc120\uc758 \uc218\ub97c \uc77d\uace0 \uac01 \uac04\uc120\uc5d0 \ub300\ud55c \uc815\ubcf4\ub97c \uc800\uc7a5\ud569\ub2c8\ub2e4. \uc774\ud6c4 \uac04\uc120\uc744 \uac00\uc911\uce58\uc5d0 \ub530\ub77c \uc815\ub82c\ud558\uace0, \uc720\ub2c8\uc628-\ud30c\uc778\ub4dc \uc790\ub8cc\uad6c\uc870\ub97c \uc0ac\uc6a9\ud558\uc5ec \uc0ac\uc774\ud074\uc744 \ud615\uc131\ud558\uc9c0 \uc54a\ub294 \uac04\uc120\uc744 \uc120\ud0dd\ud569\ub2c8\ub2e4. \ucd5c\uc885\uc801\uc73c\ub85c, \uc120\ud0dd\ub41c \uac04\uc120\uc758 \uac00\uc911\uce58 \ud569\uc744 \ucd9c\ub825\ud569\ub2c8\ub2e4.<\/p>\n
7. \uc2dc\uac04 \ubcf5\uc7a1\ub3c4<\/h2>\n
\ud06c\ub8e8\uc2a4\uce7c \uc54c\uace0\ub9ac\uc998\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 \uc77c\ubc18\uc801\uc73c\ub85c O(E log E)<\/code>\ub85c, \uc774\ub294 \uac04\uc120 \uc815\ub82c\uc5d0 \ub300\ud55c \ubcf5\uc7a1\ub3c4\uc785\ub2c8\ub2e4. \uc720\ub2c8\uc628-\ud30c\uc778\ub4dc \uc5f0\uc0b0\uc740 \ub9e4\uc6b0 \ud6a8\uc728\uc801\uc774\uba70 \uac70\uc758 \uc0c1\uc218 \uc2dc\uac04\uc5d0 \uc218\ud589\ub429\ub2c8\ub2e4.<\/p>\n8. \ub9c8\ubb34\ub9ac<\/h2>\n
\ucd5c\uc18c \uc2e0\uc7a5 \ud2b8\ub9ac\ub294 \uadf8\ub798\ud504 \uc774\ub860\uc5d0\uc11c \uc911\uc694\ud55c \uac1c\ub150\uc73c\ub85c, \ub2e4\uc591\ud55c \ucd5c\uc801\ud654 \ubb38\uc81c\uc5d0 \ud65c\uc6a9\ub429\ub2c8\ub2e4. \ud06c\ub8e8\uc2a4\uce7c\uacfc \ud504\ub9bc \uc54c\uace0\ub9ac\uc998\uc744 \uc774\ud574\ud558\uace0 \uad6c\ud604\ud568\uc73c\ub85c\uc368 \ucd5c\uc18c \uc2e0\uc7a5 \ud2b8\ub9ac\ub97c \uc27d\uac8c \uad6c\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc774\ubc88 \uac15\uc88c\ub97c \ud1b5\ud574 MST\uc758 \uac1c\ub150\uc744 \uc219\uc9c0\ud558\uace0, \uc2e4\uc81c \ucf54\ub529\ud14c\uc2a4\ud2b8 \ubb38\uc81c\uc5d0 \uc801\uc6a9\ud560 \uc218 \uc788\ub294 \ub2a5\ub825\uc744 \ud0a4\uc6b0\uae38 \ubc14\ub78d\ub2c8\ub2e4.<\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"