๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ - ํฌ๋ฃจ์ค์นผ, ํ๋ฆผ(์ต์ ์ ์ฅ ํธ๋ฆฌ)
๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ ์ต์ ์ ์ฅ ํธ๋ฆฌ ์๊ณ ๋ฆฌ์ฆ์ธ
ํฌ๋ฃจ์ค์นผ๊ณผ ํ๋ฆผ ์๊ณ ๋ฆฌ์ฆ์ ๋ํด์ ๊ณต๋ถํ ๋ด์ฉ ์ ๋ฆฌ ์
๋๋ค !
1. ์ต์ ์ ์ฅ ํธ๋ฆฌ
2. ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ
3. ํ๋ฆผ ์๊ณ ๋ฆฌ์ฆ
1. ์ต์ ์ ์ฅ ํธ๋ฆฌ
๊ทธ๋ํ์์ ์ฌ์ดํด์ด ์์ด ๋ชจ๋ ์ ๋ค์ ์ฐ๊ฒฐ์ํจ ํธ๋ฆฌ๋ค ์ค ์ ๋ถ์ ๊ฐ์ค์น ํฉ์ด ์ต์์ธ ํธ๋ฆฌ
ํ๋์ ๊ทธ๋ํ์์ ์ฌ๋ฌ ๊ฐ์ ํธ๋ฆฌ๊ฐ ๋์ฌ ์ ์๋ค.
2. ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ
๊ฐ์ค์น๊ฐ ๊ฐ์ฅ ์์ ์ ๋ถ์ด ์ฌ์ดํด์ ๋ง๋ค์ง ์์ ๋๋ง ์์ฌ๋ด์ด ๊ทธ ์ ๋ถ์ ์ถ๊ฐ์ํจ๋ค.
n๊ฐ์ ํธ๋ฆฌ๋ค์ด ์ ์ฐจ ํฉ์ณ์ ธ์ 1๊ฐ์ ์ ์ฅ ํธ๋ฆฌ๊ฐ ๋๋ค.
์์ ๊ทธ๋ํ์ ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ์ ์ ์ฉํด๋ณด๊ฒ ๋ค.
๋จผ์ , ์ ๋ถ์ ๊ฐ์ค์น๊ฐ ์์ ์์๋๋ก ์ ๋ ฌํ๋ค.
๋ค์์ผ๋ก ๊ฐ์ฅ ์ฒซ ๋ฒ์งธ ์ ๋ถ์ ๊ณ ๋ฅธ ํ, ์ฌ์ดํด์ ํ์ฑํ๋์ง ์ฒดํฌํ๊ณ ์ถ๊ฐ์ํจ๋ค.
์์ ๊ณผ์ ์ ๋ฐ๋ณตํ๋ฉด ์ต์ ์ ์ฅ ํธ๋ฆฌ๋ฅผ ๊ตฌํ ์ ์๋ค.
import java.util.*;
class Edge {
char start;
char end;
int weight;
public Edge(char start, char end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
}
class Main {
public static int find(int[] parent, int x) {
if (parent[x] == x) {
return x;
}
return parent[x] = find(parent, parent[x]);
}
public static void union(int[] parent, int x, int y) {
int rootX = find(parent, x);
int rootY = find(parent, y);
if (rootX != rootY) {
parent[rootY] = rootX;
}
}
public static boolean isCycle(int[] parent, Edge edge) {
int startParent = find(parent, edge.start - 'a');
int endParent = find(parent, edge.end - 'a');
if (startParent == endParent) {
return true;
}
union(parent, startParent, endParent);
return false;
}
public static void main(String[] args) {
int[] parent = new int[6];
for (int i = 0; i < 6; i++) {
parent[i] = i;
}
List<Edge> edges = new ArrayList<>();
edges.add(new Edge('b', 'c', 1));
edges.add(new Edge('c', 'f', 1));
edges.add(new Edge('b', 'f', 2));
edges.add(new Edge('a', 'd', 2));
edges.add(new Edge('d', 'e', 3));
edges.add(new Edge('a', 'e', 4));
edges.add(new Edge('b', 'd', 4));
edges.add(new Edge('d', 'f', 7));
edges.add(new Edge('a', 'b', 8));
edges.add(new Edge('e', 'f', 9));
List<Edge> selectedEdges = new ArrayList<>();
for (Edge edge : edges) {
if (!isCycle(parent, edge)) {
selectedEdges.add(edge);
}
}
for (Edge edge : selectedEdges) {
System.out.println("Selected edge: " + edge.start + " -> " + edge.end + ", weight: " + edge.weight);
}
}
}
์ต์ข
์ฝ๋๋ ์ด๋ ๊ฒ ์์ฑํ ์ ์๋ค.
์๊ณ ๋ฆฌ์ฆ ์์
์๊ฐ์๋ ๋ชจ๋ ์ฝ๋๋ฅผ c๋ก ์์ฑํด๋ณธ ๊ฒฝํ์ด ์๊ธฐ ๋๋ฌธ์ ์ด๋ฒ์๋ java๋ก ์์ฑํ๋ค.
์ง๊ธ์ ์ฝ๋์์๋ ๊ฐ์ค์น๋ฅผ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ฆฌํด์ ์ฝ์
ํด์ ๋ฌธ์ ๊ฐ ์์ง๋ง,
๋ค๋ฅธ ๋ฌธ์ ๋ฅผ ํ ๋๋ ๊ฐ์ค์น ์ ๋ ฌ ์ฝ๋๋ฅผ ์ถ๊ฐํ๋ ๊ฒ์ด ํ์ํ๋ค.
3. ํ๋ฆผ ์๊ณ ๋ฆฌ์ฆ
ํ๋ฆผ ์๊ณ ๋ฆฌ์ฆ(๊ทธ๋ฆฌ๋+๋์ ๊ณํ)์ ์์์ ์ ํ๋๋ฅผ ์ ํํ ํ, (n-1)๊ฐ์ ์ ๋ถ์ ํ๋ ์ฉ ์ถ๊ฐ์์ผ ํธ๋ฆฌ๋ฅผ ๋ง๋ ๋ค.
1๊ฐ์ ํธ๋ฆฌ๊ฐ ์๋ผ๋์ ์ ์ฅ ํธ๋ฆฌ๊ฐ ๋๋ค.
์์ ๊ทธ๋ํ์ ํ๋ฆผ ์๊ณ ๋ฆฌ์ฆ์ ์ ์ฉํด๋ณด๊ฒ ๋ค.
๋จผ์ , ์์์ ์ ํ๋๋ฅผ ์ ํํ์ฌ ๋ฐฐ์ด์ ๋ฃ๋๋ค.
๋ฐฐ์ด์ ์ํ์ง ์์ ์ ์ ๋ํ์ฌ, ๊ฐ์ค์น๊ฐ ์ต์์ธ ์ ์ ์ ํํ๋ค.
์์ ๊ณผ์ ์ ๋ฐ๋ณตํ๋ฉด ์ต์ ์ ์ฅ ํธ๋ฆฌ๋ฅผ ๊ตฌํ ์ ์๋ค.
์ ๋ง ํท๊ฐ๋ ธ๋ ์๊ณ ๋ฆฌ์ฆ 2๊ฐ์ง๋ฅผ ๊ณต๋ถํ๋ค.
๋ค์ ํฌ์คํ
์์ ๋ง๋์ !