{"id":28304,"date":"2024-10-27T15:33:29","date_gmt":"2024-10-27T15:33:29","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=28304"},"modified":"2024-11-26T07:04:41","modified_gmt":"2024-11-26T07:04:41","slug":"%ec%8a%a4%ec%9c%84%ed%94%84%ed%8a%b8-%ec%bd%94%eb%94%a9%ed%85%8c%ec%8a%a4%ed%8a%b8-%ea%b0%95%ec%a2%8c-%ec%b5%9c%ec%86%8c-%ec%8b%a0%ec%9e%a5-%ed%8a%b8%eb%a6%ac","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/28304\/","title":{"rendered":"\uc2a4\uc704\ud504\ud2b8 \ucf54\ub529\ud14c\uc2a4\ud2b8 \uac15\uc88c, \ucd5c\uc18c \uc2e0\uc7a5 \ud2b8\ub9ac"},"content":{"rendered":"

<\/p>\n

\n
\n

\uc774 \uae00\uc5d0\uc11c\ub294 \ucd5c\uc18c \uc2e0\uc7a5 \ud2b8\ub9ac(Minimum Spanning Tree, MST)\uc5d0 \ub300\ud574 \uc54c\uc544\ubcf4\uace0, \uc774\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud55c \uc54c\uace0\ub9ac\uc998\uc778 \ud06c\ub8e8\uc2a4\uce7c \uc54c\uace0\ub9ac\uc998(Kruskal’s Algorithm)\uc744 \uc2a4\uc704\ud504\ud2b8\ub85c \uad6c\ud604\ud574\ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \ucd5c\uc18c \uc2e0\uc7a5 \ud2b8\ub9ac\ub294 \uc8fc\uc5b4\uc9c4 \uadf8\ub798\ud504\uc5d0\uc11c \ubaa8\ub4e0 \uc815\uc810\uc744 \uc5f0\uacb0\ud558\uba70, \uac00\uc911\uce58\uc758 \ud569\uc774 \ucd5c\uc18c\uac00 \ub418\ub294 \ud2b8\ub9ac\uc785\ub2c8\ub2e4.<\/p>\n<\/header>\n

\n

\ubb38\uc81c \uc124\uba85<\/h2>\n

\ud68c\uc0ac\uac00 \uc5ec\ub7ec \ub3c4\uc2dc\ub97c \uc5f0\uacb0\ud558\ub294 \ub124\ud2b8\uc6cc\ud06c\ub97c \uad6c\uc131\ud558\ub824\uace0 \ud569\ub2c8\ub2e4. \uac01 \ub3c4\uc2dc \uc0ac\uc774\uc758 \ub3c4\ub85c\ub294 \ube44\uc6a9\uc774 \ubc1c\uc0dd\ud569\ub2c8\ub2e4. \ubaa8\ub4e0 \ub3c4\uc2dc\ub97c \uc5f0\uacb0\ud558\ub418 \ube44\uc6a9\uc744 \ucd5c\uc18c\ub85c \uc904\uc774\uae30 \uc704\ud574 \ud68c\uc0ac\ub294 \uc5b4\ub5a4 \ub3c4\ub85c\ub97c \uc120\ud0dd\ud574\uc57c \ud560\uae4c\uc694?<\/p>\n

\ub3c4\uc2dc\uc640 \ub3c4\ub85c\uc758 \uc815\ubcf4\ub97c \ub2f4\uace0 \uc788\ub294 \uadf8\ub798\ud504\uac00 \uc8fc\uc5b4\uc9c8 \ub54c, \ucd5c\uc18c \uc2e0\uc7a5 \ud2b8\ub9ac\ub97c \uad6c\ud558\ub294 \ubb38\uc81c\ub97c \ud574\uacb0\ud574\uc57c \ud569\ub2c8\ub2e4.<\/p>\n<\/section>\n

\n

\uc785\ub825 \ud615\uc2dd<\/h2>\n
\n            \uccab\uc9f8 \uc904\uc5d0 \ub3c4\uc2dc\uc758 \uac1c\uc218 N (2 \u2264 N \u2264 1000)\uacfc \ub3c4\ub85c\uc758 \uac1c\uc218 M (1 \u2264 M \u2264 10000)\uc774 \uc8fc\uc5b4\uc9d1\ub2c8\ub2e4.\n            \uc774\uc5b4\uc11c M\uac1c\uc758 \uc904\uc5d0 \uac01 \ub3c4\ub85c\uc640 \uadf8 \uac00\uc911\uce58\uac00 \uc8fc\uc5b4\uc9d1\ub2c8\ub2e4. \n            \ub3c4\ub85c\uc758 \uc815\ubcf4\ub97c (A, B, C) \ud615\ud0dc\ub85c \ub098\ud0c0\ub0b4\uba70, A\uc640 B\ub294 \ub3c4\uc2dc\uc758 \ubc88\ud638, C\ub294 \ub3c4\ub85c\uc758 \ube44\uc6a9\uc785\ub2c8\ub2e4.\n            <\/pre>\n<\/section>\n
\n
\ucd9c\ub825 \ud615\uc2dd<\/h2>\n
\n            \ucd5c\uc18c \uc2e0\uc7a5 \ud2b8\ub9ac\ub97c \uad6c\uc131\ud558\ub294 \ub370 \ud544\uc694\ud55c \ucd1d \ube44\uc6a9\uc744 \ucd9c\ub825\ud569\ub2c8\ub2e4.\n            <\/pre>\n<\/section>\n
\n
\ubb38\uc81c \ud574\uacb0 \uacfc\uc815<\/h2>\n
1\ub2e8\uacc4: \uc54c\uace0\ub9ac\uc998 \uc120\ud0dd<\/h3>\n
\uc774 \ubb38\uc81c\ub294 \ud06c\ub8e8\uc2a4\uce7c \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud558\uc5ec \ud574\uacb0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \ud06c\ub8e8\uc2a4\uce7c \uc54c\uace0\ub9ac\uc998\uc740 \uadf8\ub798\ud504\uc758 \ubaa8\ub4e0 \uac04\uc120\uc744 \uac00\uc911\uce58\uc758 \uc624\ub984\ucc28\uc21c\uc73c\ub85c \uc815\ub82c\ud55c \ud6c4, Union-Find \uc790\ub8cc\uad6c\uc870\ub97c \uc0ac\uc6a9\ud558\uc5ec \uc0ac\uc774\ud074\uc744 \uccb4\ud06c\ud558\uba70 \ucd5c\uc18c \uc2e0\uc7a5 \ud2b8\ub9ac\ub97c \uad6c\uc131\ud574 \ub098\uac00\ub294 \ubc29\uc2dd\uc785\ub2c8\ub2e4.<\/p>\n
2\ub2e8\uacc4: \ub370\uc774\ud130 \uad6c\uc870 \uc124\uacc4<\/h3>\n
Union-Find \uc790\ub8cc\uad6c\uc870\ub97c \uc0ac\uc6a9\ud558\uae30 \uc704\ud574 \ub450 \uac00\uc9c0 \ubc30\uc5f4\uc744 \ub9cc\ub4ed\ub2c8\ub2e4: parent<\/strong>\uc640 rank<\/strong>. parent<\/strong>\ub294 \uac01 \ub178\ub4dc\uc758 \ubd80\ubaa8\ub97c \ub098\ud0c0\ub0b4\uace0, rank<\/strong>\ub294 \ud2b8\ub9ac\uc758 \ub192\uc774\ub97c \ub098\ud0c0\ub0c5\ub2c8\ub2e4. \uc774 \ub370\uc774\ud130\ub97c \ud65c\uc6a9\ud558\uc5ec \ub178\ub4dc\uc758 \uc5f0\uacb0 \uc0c1\ud0dc\ub97c \uad00\ub9ac\ud569\ub2c8\ub2e4.<\/p>\n
\n            \/\/ Union-Find \uad6c\uc870\uccb4\n            struct UnionFind {\n                var parent: [Int]\n                var rank: [Int]\n\n                init(size: Int) {\n                    parent = Array(0.. Int {\n                    if parent[u] != u {\n                        parent[u] = find(parent[u])\n                    }\n                    return parent[u]\n                }\n\n                mutating func union(_ u: Int, _ v: Int) {\n                    let rootU = find(u)\n                    let rootV = find(v)\n\n                    if rootU != rootV {\n                        if rank[rootU] > rank[rootV] {\n                            parent[rootV] = rootU\n                        } else if rank[rootU] < rank[rootV] {\n                            parent[rootU] = rootV\n                        } else {\n                            parent[rootV] = rootU\n                            rank[rootU] += 1\n                        }\n                    }\n                }\n            }\n            <\/size)><\/pre>\n
3\ub2e8\uacc4: \ud06c\ub8e8\uc2a4\uce7c \uc54c\uace0\ub9ac\uc998 \uad6c\ud604<\/h3>\n
\ubaa8\ub4e0 \uac04\uc120\uc744 \uac00\uc911\uce58 \uae30\uc900\uc73c\ub85c \uc815\ub82c\ud55c \ub2e4\uc74c, \uc21c\uc11c\ub300\ub85c \uac04\uc120\uc744 \uc120\ud0dd\ud558\uba74\uc11c \uc0ac\uc774\ud074\uc744 \ud615\uc131\ud558\uc9c0 \uc54a\ub294 \uacbd\uc6b0\uc5d0\ub9cc \uc120\ud0dd\ud569\ub2c8\ub2e4. \uc774 \uacfc\uc815\uc744 \ud1b5\ud574 \ucd5c\uc18c \uc2e0\uc7a5 \ud2b8\ub9ac\ub97c \uad6c\uc131\ud558\uace0 \uc774\ub54c\uc758 \uac00\uc911\uce58 \ud569\uc744 \uacc4\uc0b0\ud569\ub2c8\ub2e4.<\/p>\n
\n            func kruskal(n: Int, edges: [(Int, Int, Int)]) -> Int {\n                var uf = UnionFind(size: n)\n                var totalCost = 0\n                let sortedEdges = edges.sorted { $0.2 < $1.2 }\n                \n                for edge in sortedEdges {\n                    let (u, v, cost) = edge\n                    if uf.find(u) != uf.find(v) {\n                        uf.union(u, v)\n                        totalCost += cost\n                    }\n                }\n                return totalCost\n            }\n            <\/pre>\n
4\ub2e8\uacc4: \ud14c\uc2a4\ud2b8 \ubc0f \uacb0\ub860<\/h3>\n
\uc774\uc81c \uc785\ub825\uc744 \ubc1b\uc544\uc11c kruskal \ud568\uc218\uc5d0 \uc804\ub2ec\ud558\uace0 \uacb0\uacfc\ub97c \ucd9c\ub825\ud574\ubd05\ub2c8\ub2e4.<\/p>\n
\n            let n = 4\n            let edges = [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)]\n            let minCost = kruskal(n: n, edges: edges)\n            print(\"\ucd5c\uc18c \uc2e0\uc7a5 \ud2b8\ub9ac\uc758 \ube44\uc6a9: \\(minCost)\")\n            <\/pre>\n
\uc704 \uc608\uc2dc\ub294 \ucd5c\uc18c \uc2e0\uc7a5 \ud2b8\ub9ac\uc758 \ucd1d \ube44\uc6a9\uc744 \ucd9c\ub825\ud574\uc90d\ub2c8\ub2e4.<\/p>\n<\/section>\n