\n \uc774\ubc88 \uae00\uc5d0\uc11c\ub294 \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ub97c \ud1b5\ud574 \uc720\ub2c8\uc628 \ud30c\uc778\ub4dc(Union-Find)<\/strong> \uc790\ub8cc\uad6c\uc870\uc5d0 \ub300\ud574 \uc0c1\uc138\ud788 \n \uc720\ub2c8\uc628 \ud30c\uc778\ub4dc\ub294 ‘\uc11c\ub85c\uc18c \uc9d1\ud569(Disjoint Set)’\uc744 \uad00\ub9ac\ud558\uae30 \uc704\ud55c \uc790\ub8cc \uad6c\uc870\ub85c, \uc8fc\ub85c \uadf8\ub798\ud504\uc5d0\uc11c \uc5f0\uacb0 \uc694\uc18c\ub97c \n \uc9c0\uae08\ubd80\ud130 \ud574\uacb0\ud574\ubcfc \ubb38\uc81c\ub294 \uc5f0\uacb0 \uc694\uc18c\uc758 \uac1c\uc218 \uad6c\ud558\uae30<\/strong>\uc785\ub2c8\ub2e4. \uc8fc\uc5b4\uc9c4 \n \uc608\ub97c \ub4e4\uc5b4, \uc544\ub798\uc640 \uac19\uc740 \uadf8\ub798\ud504\ub97c \uc0dd\uac01\ud574 \ubd05\uc2dc\ub2e4. \ub9cc\uc57d \uc815\uc810\uc774 5\uac1c\uc774\uace0 \uac04\uc120\uc774 \uc544\ub798\uc640 \uac19\ub2e4\uba74,<\/p>\n \uc5ec\uae30\uc11c \uc5f0\uacb0 \uc694\uc18c\ub294 {1, 2, 3, 4}\uc640 {5}\ub85c \ub450 \uac1c \uc788\uc2b5\ub2c8\ub2e4.\n <\/p>\n \n \uc720\ub2c8\uc628 \ud30c\uc778\ub4dc\ub97c \uc0ac\uc6a9\ud558\uc5ec \uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uac01 \ub178\ub4dc\ub97c \ubc29\ubb38\ud558\uba74\uc11c \ud574\ub2f9 \ub178\ub4dc\uac00 \uc5b4\ub5a4 \uc9d1\ud569\uc5d0 \n \uc720\ub2c8\uc628 \ud30c\uc778\ub4dc\ub97c \uad6c\ud604\ud558\uae30 \uc704\ud574 \ub450 \uac00\uc9c0 \ud568\uc218\ub97c \uc815\uc758\ud560 \uac83\uc785\ub2c8\ub2e4. \ud558\ub098\ub294 \n \uc704 \ucf54\ub4dc\ub294 \n \uc720\ub2c8\uc628 \ud30c\uc778\ub4dc\ub294 \uadf8\ub798\ud504 \ubb38\uc81c\uc5d0\uc11c \ub9e4\uc6b0 \uc720\uc6a9\ud55c \uc790\ub8cc \uad6c\uc870\uc785\ub2c8\ub2e4. \uc55e\uc11c \uc81c\uc2dc\ud55c \uc5f0\uacb0 \uc694\uc18c \uac1c\uc218 \uad6c\ud558\uae30 <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"
\n \uc124\uba85\ud558\uace0 \uc774\ub97c \uc790\ubc14\ub85c \uad6c\ud604\ud574\ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \ud2b9\ud788 \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c \uc790\uc8fc \ucd9c\uc81c\ub418\ub294 \uc720\ud615\uc758 \ubb38\uc81c\ub97c \uc120\ud0dd\ud558\uc5ec
\n \uc2e4\uc81c \ucf54\ub4dc\ub97c \uc791\uc131\ud574\ubcf4\ub294 \uacfc\uc815\uc744 \uc9c4\ud589\ud558\uaca0\uc2b5\ub2c8\ub2e4.\n <\/p>\n\uc720\ub2c8\uc628 \ud30c\uc778\ub4dc\ub780?<\/h2>\n
\n \ucc3e\uac70\ub098 \ud2b9\uc815 \ub450 \uc6d0\uc18c\uac00 \uac19\uc740 \uc9d1\ud569\uc5d0 \uc18d\ud558\ub294\uc9c0\ub97c \ud310\ub2e8\ud558\ub294 \ub370 \uc720\uc6a9\ud569\ub2c8\ub2e4. \uc774 \uc790\ub8cc\uad6c\uc870\uc758 \uc8fc\uc694 \uc5f0\uc0b0\uc740 \ub450 \uac00\uc9c0\uc785\ub2c8\ub2e4.\n <\/p>\n\n
\uc54c\uace0\ub9ac\uc998 \ubb38\uc81c \uc124\uba85<\/h2>\n
n<\/code>\uac1c\uc758
\n \uc815\uc810\uacfc m<\/code>\uac1c\uc758 \uac04\uc120\uc774 \uc788\uc744 \ub54c, \uc5f0\uacb0 \uc694\uc18c\uc758 \uac1c\uc218\ub97c \uad6c\ud558\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4. \uc5f0\uacb0 \uc694\uc18c\ub780,
\n \uadf8\ub798\ud504\uc5d0\uc11c \uc11c\ub85c \uc5f0\uacb0\ub41c \uc815\uc810\ub4e4\uc758 \uc9d1\ud569\uc744 \uc758\ubbf8\ud569\ub2c8\ub2e4.\n <\/p>\n\n 1 - 2\n | |\n 3 - 4\n 5\n <\/pre>\n
\ubb38\uc81c \uc815\uc758<\/h2>\n
\n \uc8fc\uc5b4\uc9c4 \uc815\uc810 n\uacfc \uac04\uc120\uc758 \ub9ac\uc2a4\ud2b8 edges\uac00 \uc788\uc744 \ub54c, \uc5f0\uacb0 \uc694\uc18c\uc758 \uac1c\uc218\ub97c \ucd9c\ub825\ud558\uc2dc\uc624.\n\n \uc785\ub825: \n n = 5\n edges = [[1, 2], [1, 3], [2, 4]]\n\n \ucd9c\ub825: 2\n <\/pre>\n
\ubb38\uc81c \ud480\uc774 \uc811\uadfc<\/h2>\n
\n \uc18d\ud558\ub294\uc9c0\ub97c \uccb4\ud06c\ud558\uace0, \uc0c8\ub85c\uc6b4 \uc5f0\uacb0\uc774 \ubc1c\uacac\ub418\uba74 \uc774\ub97c \uc720\ub2c8\uc628 \uc5f0\uc0b0\uc744 \ud1b5\ud574 \uc9d1\ud569\uc5d0 \ud1b5\ud569\ud569\ub2c8\ub2e4. \ub9c8\uc9c0\ub9c9\uc5d0\ub294
\n \uc11c\ub85c \ub2e4\ub978 \uc9d1\ud569\uc758 \uac1c\uc218\ub97c \uc138\uc5b4 \uc5f0\uacb0 \uc694\uc18c\uc758 \uac1c\uc218\ub97c \uad6c\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n <\/p>\n\uc720\ub2c8\uc628 \ud30c\uc778\ub4dc \uad6c\ud604<\/h2>\n
find<\/code> \ud568\uc218\ub294
\n \ud2b9\uc815 \uc6d0\uc18c\uc758 \ubd80\ubaa8\ub97c \ucc3e\uc544\uc8fc\uace0, \ub2e4\ub978 \ud558\ub098\ub294 union<\/code> \ud568\uc218\ub294 \ub450 \uc6d0\uc18c\ub97c \uc5f0\uacb0\ud574\uc8fc\ub294 \uc5ed\ud560\uc744 \ud569\ub2c8\ub2e4.\n <\/p>\n\uc790\ubc14 \ucf54\ub4dc \uad6c\ud604<\/h3>\n
\n public class UnionFind {\n private int[] parent;\n private int[] rank;\n\n public UnionFind(int n) {\n parent = new int[n + 1];\n rank = new int[n + 1];\n for (int i = 1; i <= n; i++) {\n parent[i] = i; \/\/ \uac01 \ub178\ub4dc\uc758 \ubd80\ubaa8\ub97c \uc790\uae30 \uc790\uc2e0\uc73c\ub85c \ucd08\uae30\ud654\n rank[i] = 0; \/\/ \ucd08\uae30 \ub7ad\ud06c\ub294 0\n }\n }\n\n public int find(int x) {\n if (parent[x] != x) {\n parent[x] = find(parent[x]); \/\/ \uacbd\ub85c \uc555\ucd95\n }\n return parent[x];\n }\n\n public void union(int x, int y) {\n int rootX = find(x);\n int rootY = find(y);\n if (rootX != rootY) {\n if (rank[rootX] > rank[rootY]) {\n parent[rootY] = rootX;\n } else if (rank[rootX] < rank[rootY]) {\n parent[rootX] = rootY;\n } else {\n parent[rootY] = rootX;\n rank[rootX]++;\n }\n }\n }\n\n public int countComponents(int n, int[][] edges) {\n \/\/ \uac04\uc120\uc73c\ub85c \uc720\ub2c8\uc628 \uc5f0\uc0b0 \uc2dc\ud589\n for (int[] edge : edges) {\n union(edge[0], edge[1]);\n }\n \/\/ \uc5f0\uacb0 \uc694\uc18c\uc758 \uac1c\uc218 \uc138\uae30\n HashSet\uba54\uc778 \ud568\uc218<\/h3>\n
\n public class Main {\n public static void main(String[] args) {\n UnionFind uf = new UnionFind(5);\n int[][] edges = {{1, 2}, {1, 3}, {2, 4}};\n int result = uf.countComponents(5, edges);\n System.out.println(\"\uc5f0\uacb0 \uc694\uc18c\uc758 \uac1c\uc218: \" + result); \/\/ \ucd9c\ub825: 2\n }\n }\n <\/pre>\n\ucf54\ub4dc \ubd84\uc11d<\/h2>\n
UnionFind<\/code> \ud074\ub798\uc2a4\ub97c \ub9cc\ub4e4\uc5b4 \uc720\ub2c8\uc628 \ud30c\uc778\ub4dc \uc54c\uace0\ub9ac\uc998\uc744 \uad6c\ud604\ud558\uc600\uc2b5\ub2c8\ub2e4.
\n \uc0dd\uc131\uc790\uc5d0\uc11c\ub294 \uac01 \ub178\ub4dc\uc758 \ucd08\uae30 \uac12\uacfc \ub7ad\ud06c\ub97c \uc124\uc815\ud558\uace0, find<\/code>\uc640 union<\/code> \ud568\uc218\ub97c
\n \uad6c\ud604\ud588\uc2b5\ub2c8\ub2e4. find<\/code>\ub294 \uacbd\ub85c \uc555\ucd95 \uae30\ubc95\uc744 \uc774\uc6a9\ud574 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub97c \uc904\uc774\uace0, union<\/code>
\n \ubc29\uc2dd\uc73c\ub85c \ub7ad\ud06c\ub97c \uc0ac\uc6a9\ud558\uc5ec \ud56d\uc0c1 \uade0\ud615\uc744 \uc720\uc9c0\ud558\ub3c4\ub85d \ud588\uc2b5\ub2c8\ub2e4.\n <\/p>\n\uacb0\ub860<\/h2>\n
\n \ubb38\uc81c\ub97c \ud1b5\ud574 \uc720\ub2c8\uc628 \ud30c\uc778\ub4dc\uc758 \uae30\ucd08\ub97c \ub2e4\uc9c8 \uc218 \uc788\uc5c8\uae38 \ubc14\ub78d\ub2c8\ub2e4. \uc2e4\uc81c \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c\ub3c4 \ub2e4\uc591\ud55c \ud615\ud0dc\ub85c
\n \ucd9c\uc81c\ub420 \uc218 \uc788\uc73c\ubbc0\ub85c \uc774 \uc790\ub8cc\uad6c\uc870\uc5d0 \ub300\ud55c \uc774\ud574\ub294 \ud544\uc218\uc801\uc785\ub2c8\ub2e4. \uc55e\uc73c\ub85c\ub3c4 \uc720\ub2c8\uc628 \ud30c\uc778\ub4dc\ub97c \ud65c\uc6a9\ud55c
\n \ub2e4\uc591\ud55c \ubb38\uc81c\ub97c \ud480\uc5b4\ubcf4\uba70 \ub354 \uae4a\uc774 \uc788\ub294 \uc774\ud574\ub97c \ud1b5\ud574 \uc2e4\ub825\uc744 \uc313\uae30\ub97c \ubc14\ub78d\ub2c8\ub2e4.\n <\/p>\n