View
신장 트리란? 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다.
그래프 G=(V, E)의 신장 트리는 정점 집합 V를 그대로 두고 |V|-1개만 남겨 트리가 되도록 만든 것이다. 간선들이 가중치를 갖는 그래프에서 간선 가중치의 합이 가장 작은 트리를 최소 신장 트리라 한다.
크루스칼 알고리즘
신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘을 최소 신장 트리 알고리즘이라고 한다.
먼저 모든 간선에 대하여 정렬을 수행한 뒤에 가장 거리가 짧은 간선부터 집합에 포함시키면 된다. 이때 사이클을 발생시킬 수 있는 간선의 경우, 집합에 포함시키지 않는다.
📍 알고리즘 동작 과정
1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다.
2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.
1) 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다.
2) 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다.
3. 모든 간선에 대하여 2번의 과정을 반복한다.
다음 그래프의 최소 신장 트리를 구해보자.
최소 신장 트리는 하늘색으로 칠한 간선들을 포함시키면 만들 수 있다. 최소 신장 트리는 일종 트리 자료구조이므로, 최종적으로 신장 트리에 포함되는 간선의 개수가 '노드의 개수-1'과 같다는 특징이 있다.
따라서 크루스칼 알고리즘의 핵심 원리는 가장 거리자 짧은 간선부터 차례대로 집합에 추가하면 된다는 것이다. 다만, 사이클을 발생시키는 간선은 제외하고 연결한다. 이렇게 하면 항상 최적의 해를 보장할 수 있다.
step0. 맨 처음에는 모든 간선을 정렬한다.
step1. 가장 짧은 간선을 선택한다.
-> (3, 4)가 선택되고 이것을 집합에 포함하면 된다. 다시 말해 노드 3과 노드 4에 대하여 union 함수를 수행하면 된다.
->노드 3과 노드 4를 동일한 집합에 속하도록 만든다.
step2. 그 다음으로 비용이 가장 작은 간선인 (4, 7)을 선택한다.
step3. 그 다음으로 비용이 가장 작은 간선인 (4, 6)을 선택한다.
step4. 그 다음으로 비용이 가장 작은 간선인 (6, 7)을 선택한다.
다만, 노드 6과 노드 7의 루트가 이미 동일한 집합에 포함되어 있으므로 신장 트리에 포함하지 않아야 한다.
따라서 union 함수를 호출하지 않는다.
.
.
.
step9. 그 다음으로 비용이 작은 간선 (1,5)를 선택한다.
다만, 노트 1과 노드 5의 루트가 이미 동일한 집합에 포함되어 있으므로 union 함수를 호출하지 않는다.
💻 소스코드
package graph;
import java.util.*;
class Edge implements Comparable<Edge> {
private int distance;
private int nodeA;
private int nodeB;
public Edge(int distance, int nodeA, int nodeB) {
this.distance = distance;
this.nodeA = nodeA;
this.nodeB = nodeB;
}
public int getDistance() {
return this.distance;
}
public int getNodeA() {
return this.nodeA;
}
public int getNodeB() {
return this.nodeB;
}
// 거리(비용)가 짧은 것이 높은 우선순위를 가지도록 설정
@Override
public int compareTo(Edge other) {
if (this.distance < other.distance) {
return -1;
}
return 1;
}
}
public class graph07 {
public static int v, e; // 노드의 개수(V)와 간선(Union 연산)의 개수(E)
public static int[] parent = new int[100001];
public static ArrayList<Edge> edges = new ArrayList<>();
public static int result = 0;
// 특정 원소가 속한 집합을 찾기
public static int findParent(int x) {
// 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if (x == parent[x]) return x;
return parent[x] = findParent(parent[x]);
}
// 두 원소가 속한 집합을 합치기
public static void unionParent(int a, int b) {
a = findParent(a);
b = findParent(b);
if (a < b) parent[b] = a;
else parent[a] = b;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
v = sc.nextInt();
e = sc.nextInt();
// 부모 테이블상에서, 부모를 자기 자신으로 초기화
for (int i = 1; i <= v; i++) {
parent[i] = i;
}
// 모든 간선에 대한 정보를 입력 받기
for (int i = 0; i < e; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int cost = sc.nextInt();
edges.add(new Edge(cost, a, b));
}
// 간선을 비용순으로 정렬
Collections.sort(edges);
// 간선을 하나씩 확인하며
for (int i = 0; i < edges.size(); i++) {
int cost = edges.get(i).getDistance();
int a = edges.get(i).getNodeA();
int b = edges.get(i).getNodeB();
// 사이클이 발생하지 않는 경우에만 집합에 포함
if (findParent(a) != findParent(b)) {
unionParent(a, b);
result += cost;
}
}
System.out.println(result);
}
}
크루스칼 알고리즘의 시간 복잡도
간선의 개수가 E개 일 때, O(ElogE)의 시간 복잡도를 가진다.
크루스칼 알고리즘에서 시간이 가장 오래 걸리는 부분이 간선을 정렬하는 작업인데, E개의 데이터를 정렬했을 때의 시간 복잡도는 O(ElogE)임
📚 실전문제
동물원에서 막 탈출한 원숭이 한 마리가 세상 구경을 하고 있다. 어느 날 원숭이는 '평화로운 마을'에 잠시 머물렀는데 마침 마을 사람들은 도로 공사 문제로 머리를 맞대고 회의 중이었다.
마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 길마다 길을 유지하는데 드는 유지비가 있다.
마을의 이장은 마을을 2개의 분리된 마을로 분할할 계획을 세우고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다.
그렇게 마을의 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 되었다. 일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다. 이것을 구하는 프로그램을 작성하시오.
📝 문제 해설
전체 그래프에서 2개의 최소 신장 트리를 만들어야 한다. 최소한의 비용으로 2개의 신장 트리로 분할하려면 크루스칼 알고리즘으로 최소 신장 트리를 구성하는 간선 중에서 가장 비용이 큰 간선을 제거하는 것이다. 그러면 최소 신장 트리가 2개의 부분 그래프로 나누어진다.
💻 코드
package graph;
import java.util.*;
class Edge implements Comparable<Edge> {
private int distance;
private int nodeA;
private int nodeB;
public Edge(int distance, int nodeA, int nodeB) {
this.distance = distance;
this.nodeA = nodeA;
this.nodeB = nodeB;
}
public int getDistance() {
return this.distance;
}
public int getNodeA() {
return this.nodeA;
}
public int getNodeB() {
return this.nodeB;
}
// 거리(비용)가 짧은 것이 높은 우선순위를 가지도록 설정
@Override
public int compareTo(Edge other) {
if (this.distance < other.distance) {
return -1;
}
return 1;
}
}
public class graph08 {
public static int v, e; // 노드의 개수: V 간선의 개수 : E
public static int[] parent = new int[100001];
public static ArrayList<Edge> edges = new ArrayList<>();
public static int result = 0;
// 특정 원소가 속한 집합을 찾기
public static int findParent(int x) {
// 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if (x == parent[x]) return x;
return parent[x] = findParent(parent[x]);
}
// 두 원소가 속한 집합을 합치기
public static void unionParent(int a, int b) {
a = findParent(a);
b = findParent(b);
if (a < b) parent[b] = a;
else parent[a] = b;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
v = sc.nextInt();
e = sc.nextInt();
for (int i = 1; i <= v; i++) {
parent[i] = i;
}
for (int i = 0; i < e; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int cost = sc.nextInt();
// 비용순으로 정렬하기 위해서 튜플의 첫 번째 원소를 비용으로 설정
edges.add(new Edge(cost, a, b));
}
// 간선을 비용순으로 정렬
Collections.sort(edges);
int last = 0; // 최소 신장 트리에 포함되는 간선 중에서 가장 비용이 큰 간선
// 간선을 하나씩 확인하며
for (int i = 0; i < edges.size(); i++) {
int cost = edges.get(i).getDistance();
int a = edges.get(i).getNodeA();
int b = edges.get(i).getNodeB();
// 사이클이 발생하지 않는 경우에만 집합에 포함
if (findParent(a) != findParent(b)) {
unionParent(a, b);
result += cost;
last = cost;
}
}
System.out.println(result - last);
}
}'알고리즘 > 이코테' 카테고리의 다른 글
| [그래프 이론] 이코테 어두운 길(Java) (1) | 2022.12.31 |
|---|---|
| [동적 계획법] 이코테 개미 전사(Java) (0) | 2022.12.21 |
| [알고리즘] 06-1. 기본적인 정렬 알고리즘(선택/삽입/버블) (1) | 2022.12.20 |