[java 백준] 골드 4/ 1197번 최소스패닝 트리

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

1197번: 최소 스패닝 트리

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
class Main{
    public static class Node implements Comparable<Node>{
 
 
        int to;
        int distance;
 
 
        public Node(int to,int distance){
 
            this.to=to;
            this.distance=distance;
 
 
        }
 
        @Override
        public int compareTo(Node other){
            return this.distance-other.distance;
        }
        
 
    }
 
    public static int total;
    public static int v,e;
    static List<Node>[] list;
    static boolean[] visited;
 
    public static void prim(int start){
        PriorityQueue<Node>pq=new PriorityQueue<Node>();
        pq.add(new Node(start,0));
        while(!pq.isEmpty()){
            Node node=pq.poll();
            int to=node.to;
            int distance=node.distance;
 
            if(!visited[to]){
                //인접한 노드 중 가장 가중치 작은 애를 먼저 방문(어차피 우선순위 큐이기 때문에
                //가중치 작은애가 먼저 나옴)
 
                visited[to]=true;
                total+=distance;
                for(Node next:list[to]){
                    if(!visited[next.to]){
                        pq.add(new Node(next.to,next.distance));
                    }
                }
            }
        }
 
    }
 
    public static void main(String[]args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st=new StringTokenizer(br.readLine());
        v=Integer.parseInt(st.nextToken());
        e=Integer.parseInt(st.nextToken());
        list=new ArrayList[v+1];
        visited = new boolean[v+1];
 
        for(int i=0;i<=v;i++){
            list[i]=new ArrayList<Node>();
        }
        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());
            list[a].add(new Node(b,c));
            list[b].add(new Node(a,c));
 
        }
 
        prim(1);
        System.out.println(total);
 
 
 
 
 
 
 
 
 
 
    }
}

 

 

0. 최소스패닝 트리를 풀 수 있는 알고리즘 중 프림 알고리즘을 사용한다!

1. 양방향 간선이다.

2. 아무리 queue에 넣어줬어도 queue에 넣은 이후 탐색에 의해 노드의 visited여부가 달라질 수 있음 그래서 visited 두번 검사해줄 것.

 

https://loosie.tistory.com/159

[알고리즘/ 그래프] 최소 스패닝 트리 - 크루스칼(Kruskal)과 프림(Prim) 알고리즘 (Java)