신장 트리(Spanning Tree)
그래프의 모든 정점을 연결한 트리를 말한다. 사이클이 생기지 않는 선에서 간선의 개수를 (정점 개수 - 1)개로 만드는 것으로, 하나의 그래프에서 신장 트리는 여러 형태가 나올 수 있다.
최소 신장 트리(MST; Minimum Spanning Tree)
신장 트리 중에서 간선들의 가중치 합이 최소인 트리를 말한다. 최소 신장 트리는 다음과 같은 조건을 만족한다.
1. 간선의 가중치 합이 최소이다.
2. 사이클이 없다.
3. 모든 정점이 연결되어 있으며, (정점 개수 -1)개의 간선을 가지는 트리이다.
4. 무방향 가중치 그래프이다.
도로망, 통신망, 유통망 등 비용을 최소로 해야 하는 경우, 즉 MST를 구할 때 프림 알고리즘, 크루스칼 알고리즘을 사용한다.
크루스칼 알고리즘
간선 선택 기반 알고리즘으로, 모든 간선에 대해 가중치가 가장 작은 것들을 우선으로하여 MST의 조건을 만족할 수 있는 간선을 V-1개 선택하는 방법이다. 아직 선택되지 않은 간선들 중에 가중치가 가장 작으면서 사이클을 만들지 않는 간선을 그리디하게 선택하도록 구현한다.
동작 과정
1. 그래프의 간선들을 가중치의 오름차순으로 정렬
2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택
- 이때 가중치가 가장 낮은 간선을 선택하고, 만약 사이클이 형성되는 간선이라면 다음 간선을 선택
3. 선택한 간선을 MST 집합에 추가하고 (정점 개수 - 1)개의 간선이 선택될 때까지 반복적으로 수행
구현
import java.io.*;
import java.util.*;
public class Kruskal {
static int parents[];
static int ans = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] line = br.readLine().split(" ");
int V = Integer.parseInt(line[0]); //정점의 개수
int E = Integer.parseInt(line[1]); //간선의 개수
// 정점 A, B와 이들을 연결하는 간선의 가중치가 들어온 다고 가정
int edges[][] = new int[E][3];
// 1번부터 각 정점들의 부모를 저장할 수 있도록 배열 초기화
parents = new int[V+1];
// 각 정점의 부모를 자기 자신으로 초기화
for(int i=0; i<=V; i++) parents[i] = i;
// 간선 정보를 입력받음
for(int i=0; i<E; i++) {
line = br.readLine().split(" ");
edges[i][0] = Integer.parseInt(line[0]);
edges[i][1] = Integer.parseInt(line[1]);
edges[i][2] = Integer.parseInt(line[2]);
}
//간선의 가중치를 기준으로 정렬
Arrays.sort(edges, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return Integer.compare(o1[2], o2[2]);
}
});
int cnt = 0; //연결에 성공한 간선 수
for(int i=0; i<edges.length; i++) {
//정점과 정점이 연결될 수 있는지 확인
if(union(edges[i][0], edges[i][1])) {
ans += edges[i][2]; //연결할 수 있다면 가중치를 더해줌
cnt ++; //연결에 성공한 간선 수를 1증가 시킴
}
//연결에 성공한 간선 수가 (정점-1)개이면 종료
if(cnt == V-1) break;
}
System.out.println(ans);
}
static int find(int n) {
if(parents[n] == n) return n;
return parents[n] = find(parents[n]);
}
static boolean union(int a, int b) {
int ap = find(a); //정점 a의 부모
int bp = find(b); //정점 b의 부모
// 두 정점의 부모가 같지 않다면 숫자가 작은 쪽을 부모로 설정
if(ap != bp) {
if(ap < bp)
parents[bp] = ap;
else parents[ap] = bp;
return true; //연결됨
}
return false; //연결하지 않음
}
}각 코드에 대한 설명은 주석으로 볼 수 있다. 크루스칼 알고리즘은 O(ElogV)의 시간복잡도를 가진다.
- Comparator(간선의 가중치를 기준으로 정렬할 때 사용)
객체를 비교할 수 있는 방법은 Comparable, Comparator 두 가지가 있다. 간단하게 비교하자면 Comparable은 정렬 수행시 기본적으로 적용되는 정렬 기준을 사용하고, Integer, Double, String 클래스 등을 오름차순이나 내림차순으로 정렬할 수 있다. Comparator는 기본 정렬 기준과는 특정 파라미터를 기준으로 정렬하는 등과 같을 때 사용하는 클래스이다.
- Union-find(각 정점의 부모 정점을 찾을 때 사용)
상호 배타적 집합(Disjoint Set)를 표현할 때 사용하는 알고리즘이다. 위 예시에서 사용되었듯이 크루스칼 알고리즘에서 새로 추가할 간선의 양끝 정점이 같은 집합에 속해있는지 확인하는 경우나, 두 원소가 같은 집합에 포함되어 있는지 확인하는 연산 등에 사용한다.
프림 알고리즘
정점 선택 기반의 알고리즘으로, 시작 정점을 기준으로 가중치가 가장 작은 간선과 연결된 정점을 선택하며 트리를 확장시켜나가는 방법이다. 하나의 연결 그래프에 대해 모든 정점이 트리 집합에 포함될 때까지 반복하도록 구현한다.
동작 과정
1. 탐색을 시작할 임의의 정점 하나를 선택
2. 선택한 정점과 인접하는 정점 중 최소 비용의 간선을 갖는 정점을 선택
3. 모든 정점이 선택될 때까지 반복
행렬을 이용한 구현
import java.io.*;
import java.util.Arrays;
public class PrimMatrix {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] line = br.readLine().split(" ");
int V = Integer.parseInt(line[0]); //정점의 개수
int E = Integer.parseInt(line[1]); //간선의 개수
//두 개의 정점과 이들을 연결하는 간선의 가중치 순으로 입력된다고 가정
int[][] adj = new int[V][V];
int ans = 0;
for(int i=0; i<E; i++) {
line = br.readLine().split(" ");
int a = Integer.parseInt(line[0]);
int b = Integer.parseInt(line[1]);
int l = Integer.parseInt(line[0]);
// a->b, b->a 양방향으로 연결해 줌
adj[a][b] = l;
adj[b][a] = l;
}
// 정점이 선택되었는지 기록할 배열 선언
boolean[] visited = new boolean[V];
// 현재 선택된 정점으로부터 도달할 수 있는 최소 거리를 저장할 배열
int[] dist = new int[V];
// 최소 거리를 저장할 것이므로 최댓값으로 초기화
Arrays.fill(dist, Integer.MAX_VALUE);
// 0번째 정점을 기준으로 선택했다고 가정하자. 최초 선택한 정점은 거리 0
dist[0] = 0;
// 방문 완료한 정점의 개수
int cnt = 0;
while(true) {
int min = Integer.MAX_VALUE;
int idx = 0;
for(int i=0; i<V; i++) {
//선택되지 않은 정점이고 해당 정점을 방문했을 때 더 작은 가중치를 가진다면 갱신
if(!visited[i] && dist[i] < min) {
idx = i;
min = dist[i];
}
}
// 제일 작은 가중치를 갖는 정점을 방문
visited[idx] = true;
ans += min; // 결과값에 가중치를 더함
cnt ++; //방문한 정점 개수 + 1
// cnt와 정점 개수가 같아지면 모든 정점을 처리한 것이므로 종료
if(cnt == V) break;
// 새로 방문한 정점과 연결되어 있는 다른 정점의 간선 정보 업데이트
for(int i=0; i<V; i++) {
if(!visited[i] && adj[idx][i] > 0 && dist[i] > adj[idx][i]) {
dist[i] = adj[idx][i];
}
}
}
System.out.println(ans);
}
}
우선순위큐를 이용한 구현
import java.io.*;
import java.util.*;
public class PrimPriorityQueue {
public static class Edge implements Comparable<Edge> {
int v;
int l;
public Edge(int node, int dist) {
this.v = node;
this.l = dist;
}
@Override public int compareTo(Edge e) {
return Double.compare(this.v, e.l);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] line = br.readLine().split(" ");
int V = Integer.parseInt(line[0]);
int E = Integer.parseInt(line[1]);
List<Edge> list[] = new ArrayList[V];
for(int i=0; i<V; i++) list[i] = new ArrayList<Edge>();
int ans = 0;
//간선의 정보와 가중치 입력
for(int i = 0; i < E; i++) {
line = br.readLine().split(" ");
int a = Integer.parseInt(line[0]) - 1;
int b = Integer.parseInt(line[1]) - 1;
int l = Integer.parseInt(line[2]);
// 인접 리스트 구성, 양방향으로 연결
list[a].add(new Edge(b, l));
list[b].add(new Edge(a, l));
}
// 정점이 선택되었는지 기록할 배열 선언
boolean visited[] = new boolean[V];
// 현재 선택된 정점으로부터 도달할 수 있는 최소 거리를 저장할 배열
int[] dist = new int[V];
// 최소 거리를 저장할 것이므로 최댓값으로 초기화
Arrays.fill(dist, Integer.MAX_VALUE);
// 0번째 정점을 기준으로 선택했다고 가정하자. 최초 선택한 정점은 거리 0
dist[0] = 0;
// 방문 완료한 정점의 개수
int cnt = 0;
PriorityQueue<Edge> q = new PriorityQueue<Edge>();
q.offer(new Edge(0, dist[0])); //시작노드를 넣음(시작노드는 거리가 0이어서 가장 작은 가중치를 가지므로)
while(true) {
Edge cur = q.poll(); //가장 처음에 위치한 Edge를 뺌
if(visited[cur.v]) continue; //만약 방문했던 노드라면 무시
visited[cur.v] = true; //방문하지 않은 노드는 방문했다고 표시
ans += cur.l; // 거리를 더해줌
cnt ++; //방문한 노드 개수 + 1
if(cnt == V) break; //만약 모든 노드를 방문했으면 종료
for(Edge v : list[cur.v]) { //현재 위치와 연결된 Edge를 탐색
if(!visited[v.v] && dist[v.v] > v.l) { //만약 더 작은 가중치를 가졌으면
dist[v.v] = v.l; // 연결된 Edge의 가중치를 갱신
q.offer(new Edge(v.v, dist[v.v])); // 다음으로 탐색하기 위해 큐에 삽입
}
}
}
System.out.println(ans);
}
}인접 행렬을 사용하면 O(V^2)의 시간복잡도를 가지며, 우선순위큐를 사용하면 O(ElogV)의 시간복잡도를 가진다.
프림에서 우선순위큐를 사용한다면 크루스칼 알고리즘과 시간 복잡도가 비슷하지만, 일반적으로 간선이 많을 때는 프림이 유리하고, 그렇지 않은 경우에는 크루스칼이 유리하다.
참고
'알고리즘(코딩테스트)' 카테고리의 다른 글
| 투포인터(Two Pointers) 알고리즘 (0) | 2021.10.08 |
|---|---|
| 이분탐색(Binary Search) 알고리즘 (0) | 2021.10.08 |
| 재귀/완전탐색 | 백준 15684번 사다리 조작(JAVA) - 2018 삼성 SW 역량 테스트 (0) | 2021.09.25 |
| 백준 14888번 연산자 끼워넣기(JAVA) (0) | 2021.09.24 |
| 백준 18899번 스타트와 링크(JAVA) (0) | 2021.09.24 |
댓글