최소 스패닝 트리
1. 핵심 개념 및 근거
필요한 개념 및 자료구조
- MST: 무방향 가중치 그래프에서 모든 정점을 연결하며, 가중치의 합이 최소가 되는 트리입니다.
- Prim 알고리즘: 시작 정점에서 출발하여, 현재 단계까지 연결된 정점들과 연결되지 않은 정점들 사이의 간선 중 가장 가중치가 작은 간선을 선택하여 트리를 확장하는 방식입니다.
- 우선순위 큐: 매 순간 최솟값을 빠르게 찾기 위해 사용합니다.
선택 근거 및 제약사항
- 문제 명시: 문제 제목부터 ‘최소스패닝트리’를 구하라고 명시되어 있습니다.
- 제약 사항(V = 10^5, E=10^5*2): 정점과 간선의 수가 많습니다.
- O(V^2)방식의 프림을 사용하면 시간 초과가 발생 할 수 있습니다.
- 우선순위 큐를 이용한 프림 알고리즘의 사간 복잡도는 O(ElogV)입니다.
- 10^5*2 * 17 ~= 3.4 * 10^6 연산으로 충분히 통과 가능합니다.
- 데이터 타입: 간선의 가중치는 절대값 10^6이하이지만, MST 전체 합은
int범위를 초과합니다. 따라서 MST 비용은long으로 선언해야 합니다.
2. 추론 과정
- 모든 정점을 연결: 트리 혹은 그래프 탐색 문제임을 시사합니다.
- 가중치의 합이 최소: 그리디 기반의 MST 알고리즘 확정입니다.
- 사이클이 없어야 함: 트리의 기본 속성입니다.
- V와 E의 규모: 인접 행렬은 메모리 초과가 발생하므로, 인접 리스트 또는 간선 리스트를 사용해야 함을 인지해야 합니다.
3. 설계 및 접근
- 그래프 구축: 인접 리스트에 간선 정보를 양뱡향으로 저장합니다.
- 임의의 시작점 선택: 임의의 정점(보통 1번)을 선택해 우선순위 큐에 넣습니다.
- 반복 탐색:
- 우선순위 큐에서 가중치가 가장 작은 간선을 꺼냅니다.
- 이미 방문한 정점이면 무시합니다.
- 처음 방문하는 정점이라면 가중치를 더하고, 해당 정점과 연결된 모든 간선을 우선순위 큐에 넣습니다.
- 결과 출력: MST의 가중치의 합를 출력합니다.
4. 예시 시뮬레이션
상황: 정점 3개, 간선: (1-2,가중치 5), (2-3, 가중치 3), (1-3, 가중치 10)
- 시작 1번:
visited[1] = true. 1번과 연결된 (1-2,5), (1-3,10)을 큐에 삽입 - 1회차: 큐에서 가장 작은 (1-2,5) 추출. 2번은 미방문이므로 연결.
sum = 5,visited[2] = true.- 2번과 연결된 (2-3, 3)을 큐에 삽입.
- 2회차: 큐에서 가장 작은 **(2-3, 3) 추출. 3번은 미방문이므로 연결.
sum = 5 + 3 = 8,visited[3] = true.- 3번과 연결된 간선들을 넣지만 이미 모든 정점 방문 완료
- 최종 가중치: 8
5. 주의 사항
- 자료형 주의: 가중치의 합이 정수 범위를 벗어날 수 있습니다.
int가 아닌long타입을 사용해야 합니다.
- 메모리 관리: V가 크기 때문에 인접 행렬을 만들면 메모리 초과가 발생합니다.
6. 코드 풀이
6.1 그래프 구축
// 인접 리스트 초기화
ArrayList<ArrayList<Edge>> graph = new ArrayList<>();
for (int i = 0; i <= V; i++) {
graph.add(new ArrayList<>());
}
// 간선 정보 입력
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
// 간선 연결
graph.get(a).add(new Edge(b, c));
graph.get(b).add(new Edge(a, c));
}
- 인접 리스트
ArrayList<ArrayList<Edge>에 간선 정보를 양방향으로 저장합니다.
6.2 우선순위 큐 활용
6.2.1 프림 시작
// 초기 정점을 큐에 삽입
pq.add(new Edge(1, 0));
- 임의의 정점을 선택해 PQ에 넣어서 프림을 시작합니다.
6.2.2 반복 탐색
// 더이상 작업할 수 없을 떄까지 수행
while (!pq.isEmpty()) {
// 현재 정점과 비용
Edge cur = pq.poll();
int cur_w = cur.w;
long cur_weight = cur.weight;
// 이미 방문한 정점은 다음으로 넘긴다.
if (visited[cur_w])
continue;
visited[cur_w] = true;
result += cur_weight;
// 모든 정점을 연결했다면 조기 종료 가능
if (++count == V) break;
// 인접한 정점을 방문
for (Edge edge : graph.get(cur_w)) {
// 이미 방문한 정점은 다음으로 넘긴다.
if(visited[edge.w])
continue;
pq.add(new Edge(edge.w, edge.weight));
}
}
- PQ에서 가중치가 가장 작은 간선을 꺼냅니다 (
poll). - 이미 방문한 정점이면 무시 (
visited체크). - 처음 방문하는 정점이라면 가중치를 더하고, 해당 정점과 연결된 모든 간선을 PQ에 넣습니다.
count를 통해서 모든 정점이 연결했다면 조기 종료하게 했습니다.
6.3 전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Solution {
// 간선 클래스
static class Edge implements Comparable<Edge> {
int w;
long weight;
public Edge(int w, long weight) {
super();
this.w = w;
this.weight = weight;
}
@Override
public int compareTo(Edge o) {
// TODO Auto-generated method stub
return Long.compare(this.weight, o.weight);
}
}
public static void main(String[] args) throws NumberFormatException, IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
// T 입력
int T = Integer.parseInt(br.readLine().trim());
// tc 수행
for (int tc = 1; tc <= T; tc++) {
// V, E 입력
StringTokenizer st = new StringTokenizer(br.readLine());
int V = Integer.parseInt(st.nextToken());
int E = Integer.parseInt(st.nextToken());
// 인접 리스트 초기화
ArrayList<ArrayList<Edge>> graph = new ArrayList<>();
for (int i = 0; i <= V; i++) {
graph.add(new ArrayList<>());
}
// 간선 정보 입력
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
// 간선 연결
graph.get(a).add(new Edge(b, c));
graph.get(b).add(new Edge(a, c));
}
// 방문 체크 배열 초기화
boolean[] visited = new boolean[V + 1];
// 우선순위 큐
PriorityQueue<Edge> pq = new PriorityQueue<>();
// MST의 가중치
long result = 0;
// 연결 갯수
int count = 0;
// 초기 정점을 큐에 삽입
pq.add(new Edge(1, 0));
// 더이상 작업할 수 없을 떄까지 수행
while (!pq.isEmpty()) {
// 현재 정점과 비용
Edge cur = pq.poll();
int cur_w = cur.w;
long cur_weight = cur.weight;
// 이미 방문한 정점은 다음으로 넘긴다.
if (visited[cur_w])
continue;
visited[cur_w] = true;
result += cur_weight;
// 모든 정점을 연결했다면 조기 종료 가능
if (++count == V) break;
// 인접한 정점을 방문
for (Edge edge : graph.get(cur_w)) {
// 이미 방문한 정점은 다음으로 넘긴다.
if(visited[edge.w])
continue;
pq.add(new Edge(edge.w, edge.weight));
}
}
// 출력 내용 추가
sb.append("#" + tc + " " + result + "\n");
} // tc 종료
// 출력
System.out.println(sb);
}
}