BOJ 3124. 최소 스패닝 트리

 

1. 문제 요약

최소 스패닝 트리

= 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리

 

👿 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하여라 👿

 

2. 문제 입출력

입력값

• 테스트 케이스 수 : T
• 정점의 개수 N, 간선의 개수 M
• E개의 줄에 걸쳐 간선 정보 : A, B, C

1
3 3
1 2 1
2 3 2
1 3 3

출력값

• 최소 스패닝 트리의 가중치

#1 3

 

3. 입력 제한 크기

• 시간 제한 : 10개 테스트 케이스 20초
• 1 ≤ V (정점 개수) ≤ 100,000
• 1 ≤ E (r간선 개수) ≤ 200,000
• 가중치 : 음수 가능, 절대값 1,000,000 이하

 

4. 아이디어 (접근법, 그림, 시각화)

• 프림 알고리즘

1. 임의 정점 하나 선택
2. 선택 정점과 인접하는 정점 중 가장 작은 가중치의 간선이 존재하는 정점을 선택하여 트리 확장
3. 모든 정점 선택 시까지 2번 반복

정점 1에서 시작

정점 2 선택

정점 3 선택

정점 4 선택

완성~

5. 시간 복잡도

• 인점 리스트 구성 : O(E)
• 프림 알고리즘 : O(E log V)

→ O(E log V)

→ 3093ms

 

6. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.List;
 
public class Solution {
    static int V, E;
    static List<int[]>[] adj;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
 
        int T = Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) {
            st = new StringTokenizer(br.readLine());
            // 정점 수
            V = Integer.parseInt(st.nextToken());
            // 간선 수
            E = Integer.parseInt(st.nextToken());
						
			// 인접 리스트 초기화
            adj = new ArrayList[V + 1];
            for (int i = 1; i <= V; i++) {
                adj[i] = new ArrayList<>();
            }
						
			// 간선 정보 입력받아 인접 리스트에 추가
			// 양방향
            for (int i = 0; i < E; i++) {
                st = new StringTokenizer(br.readLine());
                int u = Integer.parseInt(st.nextToken());
                int v = Integer.parseInt(st.nextToken());
                int w = Integer.parseInt(st.nextToken());
                adj[u].add(new int[]{v, w});
                adj[v].add(new int[]{u, w});
            }
						
			// 각 정점이 MST에 포함되었는지 나타내는 배열
            boolean[] visited = new boolean[V + 1];
            // 현재 고려할 수 있는 간선들을 가중치 기준으로 오름차순 관리하는 우선순위 큐
            PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
						
			// 정점 1에서 시작
            pq.offer(new int[]{1, 0});
            
            // 가중치 합
            long result = 0;
            // 연결된 정점 수
            int count = 0;
 
            while (!pq.isEmpty()) {
            
		        // 가장 작은 가중치 간선 선택
                int[] current = pq.poll();
                int u = current[0];  // 도착 정점
                int weight = current[1];  // 가중치
								
				// 이미 방문한 정점인지 확인
                if (visited[u]) {
	                continue;
	              };
								
				// 정점 방문 처리 및 결과 갱신
                visited[u] = true;
                result += weight;
                count++;
								
				// MST 완성 여부 확인
                if (count == V) {
	                break;
	              };
 
                for (int[] next : adj[u]) {
                    int v = next[0];
                    int w = next[1];
                    if (!visited[v]) {
                        pq.offer(new int[]{v, w});
                    }
                }
            }
 
            sb.append('#').append(t).append(' ').append(result).append('\n');
        }
 
        System.out.print(sb);
    }
}