프림 알고리즘은 주어진 그래프에서 MST(Minimum Spanning Tree = 최소 신장 트리)를 찾는 알고리즘이다. MST란 모든 노드를 연결하는 트리 중 간선의 가중치의 합이 가장 작은 트리를 말한다. MST를 찾는 알고리즘은 프림 알고리즘과 크루스칼 알고리즘 2개가 있는데 주어진 그래프의 노드의 개수보다 간선의 수가 훨씬 많을 때는 프림 알고리즘을 사용하는 것이 더 효율적이다.
프림 알고리즘은 다음과 같이 진행된다.
1. 어떤 노드를 방문해 방문처리를 하고 우선순위 큐에 노드와 연결된 간선들을 넣는다 (만약 간선의 도착지가 방문한 노드면 큐에 넣지 않는다)
2. 우선순위 큐는 자동으로 간선의 가중치를 기준으로 오름차순 정렬을 유지한다
3. 큐에서 빼낸 값은 가장 낮은 가중치를 갖는 간선이 되고 그 간선으로 연결된 노드를 방문한다
4. 만약 방문했던 노드면 3번으로 돌아가고 새로 방문하는 노드이면 1번으로 돌아간다
다익스트라 알고리즘과 비슷한 점이 있어서 다익스트라 알고리즘을 배웠다면 더 쉽게 이해할 수 있을 것이다. 프림 알고리즘은 그리디 알고리즘 느낌으로 어떤 노드를 방문할 때 가장 낮은 가중치를 갖는 간선을 이용하여 방문한다는 개념을 적용시킨 알고리즘이다. 모든 노드를 방문하며 노드의 간선을 전부 큐에 넣기 때문에 시간 복잡도는 O(E*logV)가 된다. (V = 노드의 개수, E = 간선의 개수)
백준 1647번 도시 분할 계획 문제를 풀어보면서 프림 알고리즘에 대해 이해해보자.
https://www.acmicpc.net/problem/1647
문제는 다음과 같다.
마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다.
마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다.
그렇게 마을의 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 되었다. 일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다. 이것을 구하는 프로그램을 작성하시오.
위의 내용을 프림 알고리즘과 결합시켜 정리해보면 마을과 길을 그래프형식으로 주었을때 MST의 가중치 합에서 MST내부의 간선 중 가장 큰 값의 가중치를 뺀 값을 출력하라는 내용이다.
따라서 아래의 코드처럼 프림 알고리즘으로 MST의 간선들을 찾으면서 가중치의 합 sum을 구하고 간선들을 찾을 때마다 가중치 최댓값 max를 갱신하여 sum - max를 출력하였다.
import java.io.*;
import java.util.*;
class bridge implements Comparable<bridge>{
int house;
int val;
bridge(int h, int v){
house = h;
val = v;
}
@Override
public int compareTo(bridge o) {
return this.val - o.val;
}
}
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
ArrayList<bridge>[] lst = new ArrayList[n + 1];
boolean[] check = new boolean[n + 1];
for (int i = 0; i < n + 1; i++)
lst[i] = new ArrayList<>();
for (int i = 0; i < m; i++){
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
lst[a].add(new bridge(b, c));
lst[b].add(new bridge(a, c));
}
PriorityQueue<bridge> q = new PriorityQueue<>();
q.add(new bridge(1, 0));
int sum = 0;
int max = 0;
while (!q.isEmpty()){
bridge now = q.poll();
int h = now.house;
int v = now.val;
if (check[h])
continue;
check[h] = true;
sum += v;
max = Math.max(v, max);
for (bridge next : lst[h]) {
if (!check[next.house])
q.add(next);
}
}
System.out.println(sum - max);
}
}
1번 노드를 최초 방문노드로 하기 위해 우선순위 큐에 넣고 while문을 시작하였다. while문의 내용은 위에서 본 프림 알고리즘의 진행순서 1, 2, 3, 4번과 같이 되어있는데 살짝 다른 점은 만약 MST의 간선을 찾은경우 sum과 max를 갱신한다는 점이다.
비트 마스킹 (BitMasking) & 백준 13701 (중복 제거) (0) | 2023.06.16 |
---|---|
HashMap 함수 (0) | 2023.05.03 |
해시법 (체인법, 오픈 주소법) (0) | 2023.04.22 |
위상 정렬 (with 백준 1005) (0) | 2023.04.20 |
이진 탐색 트리 (1) | 2023.04.18 |