1. ์๋ก์ ์งํฉ์ ๊ฐ๋ ๋ฐ ์ดํด ๐บ
1. ๊ฐ๋
- ์๋ก์ ์งํฉ์ด๋ ์๋ก ์ค๋ณต ํฌํจ๋ ์์๊ฐ ์๋ ์งํฉ์ ๋งํ๋ค.
- ๊ต์งํฉ์ด ์๋(null) ์งํฉ์ด๋ค.
2. ๋ํ์
- ์งํฉ์ ์ํ ํ๋์ ํน์ ๋ฉค๋ฒ๋ฅผ ๋ํ์๋ผ๊ณ ํ๋ค.
- ์ด๋ ์งํฉ์ ๊ตฌ๋ถํ๊ธฐ ์ํด ์ฌ์ฉ๋๋ค.
3. ์์
๋น ๋ฅธ ์ดํด๋ฅผ ์ํด ๊ฐ๋จํ ์์๋ฅผ ์ดํด๋ณด์. 5๋ช ์ ํ์(A, B, C, D, E)์ด ์๋ค๊ณ ํ์.
{A}, {B}, {C}, {D}, {E}
์๋์ ๊ฐ์ ์น๊ตฌ ๊ด๊ณ๊ฐ ์๋ค๊ณ ํ์.
A - B
B - C
D - E
์น๊ตฌ ๊ด๊ณ๋ฅผ ํตํด์ 2๊ฐ์ ์งํฉ์ ๋ง๋ค ์ ์๋ค.
G1 = {A, B, C}
G2 = {D, E}
์๋ก ์ค๋ณต ํฌํจ๋ ์์๊ฐ ์์ผ๋ฏ๋ก ์ด๋ ์๋ก์ ์งํฉ์ด๋ค. (ํ ์ฌ๋์ด ๋ถ์ ์ ์ ์จ์ ์์ชฝ ์งํฉ์ ํฌํจ๋ ์ ์์ผ๋ฏ๋ก ๋น์ฐํ ๊ฒฐ๊ณผ์ด๋ค.)
2. ํํ ๋ฐฉ๋ฒ 2๊ฐ์ง ๐
1. Linked list (์ฐ๊ฒฐ ๋ฆฌ์คํธ)
- ๊ฐ์ ์งํฉ์ ์์๋ค์ ํ๋์ ์ฐ๊ฒฐ๋ฆฌ์คํธ๋ก ๊ด๋ฆฌ๋๋ค.
- ๊ฐ ๋ฆฌ์คํธ์ ํค๋(head) ๋ถ๋ถ์ด ํด๋น ์งํฉ์ ๋ํ์์ด๋ค.
- ๋ ธ๋์ ํค๋๋ฅผ ๊ฐ๋ฆฌํค๋ ํฌ์ธํฐ๋ฅผ ํฌํจ์ํจ๋ค. (์ด์ ์์๋ฅผ ๊ฐ๋ฆฌํค๋ ๊ฒ ์๋ ๋ฐ๋ก ํค๋๋ฅผ ๊ฐ๋ฆฌํค๋ ์ด์ ๋ ๋ค์์ ๋์ค๋ Path Compression์ ๋ฐฉ๋ฒ์ ๋ณด๋ฉด ์ดํดํ ์ ์๋ค.)
2. Tree (ํธ๋ฆฌ)
- ๋ ๊ฐ์ ์์๊ฐ ๊ฐ์ ํธ๋ฆฌ์ ์กด์ฌํ๋ค๋ฉด ๊ฐ์ ์งํฉ์ ์๋ฏธํ๋ค.
- ๋ฃจํธ ๋
ธ๋๊ฐ ๋ํ์๊ฐ ๋๋ค.
(์น๊ตฌ๊ด๊ณ์ ์์์์ B์ C๋ฅผ ์ฐ๊ฒฐํ๋ ๊ณผ์ ์์ C๊ฐ A์ ๋ถ์ ์ด์ ๋ ๋ค์ ๋์ค๋ ๋ด์ฉ์ ๋ณด๋ฉด ์ดํด๊ฐ ๊ฐ๋ฅํ๋ค.)
3. ์ฐ์ฐ 3๊ฐ์ง ๐
๋ฐฐ์ด๋ก ํํํ ํธ๋ฆฌ๋ฅผ ์ด์ฉํ์ฌ ์ดํด๋ณด์. ์๋ ๋ ๊ฐ์ง๋ฅผ ์ ๊ธฐ์ตํ๋ฉด์ ์งํํด๋ณด์.
- ๋ํ์๋ ์์ ์ ๊ฐ๋ฆฌํจ๋ค.
parents[i] = i - ์์ ์ ๊ฐ๋ฆฌํค์ง ์์ผ๋ฉด ํธ๋ฆฌ๋ฅผ ํ๊ณ ์ฌ๋ผ๊ฐ๋ฉด์ ๋ํ์๋ฅผ ์ฐพ์ ์ ์๋ค.
1. makeSet()
์๊ธฐ ์์ ์ด ๋ํ์๋ก ํ๋ ๋ฐฐ์ด์ ์์ฑํ๋ค.
static void makeSet() {
parents = new int[N];
for(int i = 0; i < N; i++) {
parents[i] = i;
}
}
2. findSet(a)
a๋ฅผ ํฌํจํ๋ ์งํฉ์ ๋ํ์๋ฅผ ์ฐพ๋๋ค.
static int findSet(int a) {
if(parents[a] == a) {
return a;
}
else {
return findSet(parents[a]);
}
}
3. union(a, b)
a์ b๋ฅผ ํฌํจํ๋ ๋ ์งํฉ์ ํตํฉํ๋ค.
static void union(int a, int b) {
int aRoot = findSet(a);
int bRoot = findSet(b);
// ์ด๋ฏธ ๊ฐ์ ์งํฉ์ธ ๊ฒฝ์ฐ
if(aRoot == bRoot) {
return;
}
parents[bRoot] = aRoot;
}
4. ๊ฐ์ ์ ๐
๋ํ์๋ฅผ ์ฐพ๊ธฐ ์ํด find๋ฅผ ์ฌ์ฉํ๋ ๊ฒฝ์ฐ, ํธ๋ฆฌ์ ํ๋จ๋ถ์ ์์์๋ก ๋ ๋ง์ ํ์์ด ์๊ตฌ๋๋ค.(๋
ธ๋๋ฅผ ํ๊ณ ๊ณ์ ์ฌ๋ผ๊ฐ์ผ ํ๋ค.) ์ฆ, ํธ๋ฆฌ์ ๋์ด์ ์ํฅ์ ๋ง์ด ๋ฐ๊ฒ ๋๋ค.
ํธ๋ฆฌ์ ๋์ด๋ฅผ ์ค์ด๊ธฐ ์ํด(ํจ์จ์ฑ์ ์ฆ๊ฐ์ํค๊ธฐ ์ํด) 'Path Compression'๊ณผ 'Union By Rank'๋ฅผ ์ฌ์ฉํ ์ ์๋ค.
1. Path Compression
์ด ๋ฐฉ๋ฒ์ ๋ํ์๋ฅผ ์ฐพ๊ธฐ ์ํด ํธ๋ฆฌ๋ฅผ ํ๊ณ ์ฌ๋ผ๊ฐ๋๋ก ์ค๊ณํ๋ ๊ฒ์ด ์๋ ๋ฐ๋ก ๋ํ์๋ฅผ ๊ฐ๋ฆฌํค๋๋ก ์ค๊ณํ๋ ๊ฒ์ด๋ค.
์ด๋ find๋ฉ์๋์์ ์ฝ๊ฒ ๊ตฌํํ ์ ์๋ค.
static int findSet(int a) {
if(parents[a] == a) {
return a;
}
else {
// ๊ธฐ์กด
// return findSet(parents[a]);
// ๋ณ๊ฒฝ (Path Compression)
return parents[a] = findSet(parents[a]);
}
}
2. Union By Rank
Union By Rank๋ฅผ ์ฌ์ฉํ๊ธฐ ์ํด์ rank[]๋ผ๋ ์๋ก์ด ๋ฐฐ์ด์ด ํ์ํ๋ค. rank[i]๋ i๋ฅผ ๋ฃจํธ๋ก ํ๋ ์๋ธํธ๋ฆฌ์ ๋์ด๋ค. ๋ ์งํฉ์ ํฉ์น ๋ rank๊ฐ ๋ฎ์ ์งํฉ์ด rank๊ฐ ๋์ ์งํฉ ์๋๋ก ๋ค์ด๊ฐ๊ฒ ๋๋ค.
static void union(int a, int b) {
int aRoot = findSet(a);
int bRoot = findSet(b);
// ๊ฐ์ ์งํฉ์ธ ๊ฒฝ์ฐ
if(aRoot == bRoot) {
return;
}
int aRank = rank[aRoot];
int bRank = rank[bRoot];
if(aRank < bRank) {
parents[aRank] = bRank;
}
else if(aRank > bRank) {
parents[bRank] = aRank;
}
else {
parents[aRank] = bRank;
rank[aRank]++;
// ์์๋ฅผ ๋ฐ๊ฟ๋ ์๊ด์์
// parents[bRank] = aRank;
// rank[bRank]++;
}
}
5. ์๊ฐ๋ณต์ก๋ & ๊ณต๊ฐ๋ณต์ก๋ ๐
1. ์๊ฐ๋ณต์ก๋
- makeSet์ ์ด์ฉํ์ฌ n๊ฐ์ ์์๋ก ์งํฉ์ ์์ฑํ๋ ๋ฐ ๊ฑธ๋ฆฌ๋ ์๊ฐ : O(n)
- findSet ๋๋ union์ ์ฌ์ฉํ๋ ๋ฐ ๊ฑธ๋ฆฌ๋ ์๊ฐ : O(log n)
⇒ ์ ์ฒด ์๊ฐ ๋ณต์ก๋ : O(n + log n)
2. ๊ณต๊ฐ๋ณต์ก๋
n๊ฐ์ ์์๋ฅผ ์ ์ฅํ๋ฏ๋ก O(n)
[์ฐธ๊ณ ์๋ฃ]
Disjoint Set Data Structures - GeeksforGeeks
A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.
www.geeksforgeeks.org
'๐ ์๊ณ ๋ฆฌ์ฆ > ETC' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
์ต์ฅ๊ณตํต๋ถ๋ถ์์ด(Longest Common Subsequence - LCS) (0) | 2023.04.01 |
---|---|
์ต์ฅ๊ณตํต๋ฌธ์์ด(Longest Common Substring - LCS) (0) | 2023.04.01 |
์ต์ฅ์ฆ๊ฐ๋ถ๋ถ์์ด(Longest Increasing Subsequence - LIS) (0) | 2023.04.01 |