[BOJ] 백준 1197 최소 스패닝 트리

출처: https://www.acmicpc.net/problem/1197

 Input 

3 3

1 2 1

2 3 2

1 3 3

 

 Output 

3

Path: ① -- ② -- ③

cost:      1      2  =  3

▶ 프림(Prim) 알고리즘 구현

시작정점으로 부터 가중치가 낮은 간선으로 정점을 연결해 나가는 방법

※ 최소신장 트리 - 프림(Prim) / 크루스칼(Kruskal)

최소신장 트리 - 프림(Prim) / 크루스칼(Kruskal)

 

시뮬레이션

① 무방향 가중치 그래프 구현

    무방향이므로 인접리스트로 구현할 때, 연결된 정점에 각각에 연결된 정보를 넣어줍니다.

 

② 임의의 출발점으로부터 가중치가 가장 낮은 정점과의 간선Edge 선택

    ex) 정점 [1]을 출발점에서 시작

    ※ 우선순위 큐를 이용해 가중치가 낮은 간선Edge을 쉽게 구할 수 있습니다.

 

 

③ 현재 단계에서 연결된 정점들 중에서 가중치 가장 낮은 간선으로 방문하지 않은 정점 방문

pq = [(2-4, 35), (2-6, 38) (1-3, 41) (1-5, 60)]에서 첫번째 원소 선택

 

④ 작업 ③을 |V| - 1 만큼 반복하며, 모든 정점 |V|개를 선택(방문)

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N, M;
    static List<List<Edge>> adList; // 인접 리스트
    static boolean[] visited;
    static List<Edge> mstPath; // MST 경로
	
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new  InputStreamReader(System.in));
        StringTokenizer st = null;
        
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 정점의 개수
        M = Integer.parseInt(st.nextToken()); // 간선의 개수
        
        adList = new ArrayList<>();
        // 인덱스를 1부터 하기 위해 임의로 한 개를 넣어둠
        adList.add(new<Edge> ArrayList());
        for(int i=1; i<=N; i++) {
            adList.add(new<Edge> ArrayList());
        }
        
        while(M-- > 0) {
            st = new StringTokenizer(br.readLine());
        	int from = Integer.parseInt(st.nextToken());
        	int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            // 무방향 그래프이므로 연결된 정점에 각각 정보를 넣어줌
            adList.get(from).add(new Edge(from, to, cost));
            adList.get(to).add(new Edge(to, from, cost));
        }
        mstPath = new ArrayList<>();
        // 프림알고리즘을 통해 MST 도출
        MSTByPrim();
        
        // 정답출력
        printAnswer();
    }
     
    private static void MSTByPrim() {
        // 가중치 낮은 간선을 담기 위한 우선순위 큐
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        // 방문 대기 정점
        Queue<Integer> queue = new LinkedList<>();
    	visited = new boolean[N+1];
        
        // 출발정점으로 임의로 [1] 선택
        queue.add(1);
        
        // 대기 목록 queue가 비워질 때까지
        while(!queue.isEmpty()) {
            int current = queue.poll();
            visited[current] = true;

            for (Edge edge : adList.get(current)) {		
				if(!visited[edge.to]) {			
					pq.add(edge);
				}
            }
            
			while(!pq.isEmpty()) {
                Edge edge = pq.poll();			
                if(visited[edge.to]) continue;
				
                queue.add(edge.to);		
                visited[edge.to] = true;		
                mstPath.add(edge);				
                break;
			}
        }
	}
    
    public static void printAnswer() {
    	StringBuilder sb = new StringBuilder();
        int costSum = 0; // MST 간선들의 가중치 합
        for (int i=0; i < mstPath.size(); i++) {
        	costSum += mstPath.get(i).cost;
        }
        sb.append(costSum);
        System.out.println(sb.toString());
    }
}

class Edge implements Comparable<Edge>{
	int from, to, cost;
	
	public Edge(int from, int to, int cost) {
        this.from = from;
        this.to = to;
        this.cost = cost;
	}
	
    @Override
    public int compareTo(Edge target) {
          // 가중치가 낮은 간선이 앞쪽에 배치
          return this.cost - target.cost;
    }
}