링크

1197 최소 스패닝 트리

문제

풀이

이 문제는 MST를 공부해야 풀 수 있다.
처음에 MST를 모르고 문제만 봤을 때 플로이드와샬 알고리즘인줄 알았는데 아니였다.
플로이드 와샬은 하나의 정점에서 모든 정점으로 가는 최솟값을 구하는 것이고

MST(최소 스패닝 트리)는 간선에 가중치를 고려하여 최소 비용의 Spanning Tree를 선택하는 것이다. 즉, 네트워크(가중치를 간선에 할당한 그래프)에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 것이다.

MST는 특징이 있다.
1. 간선의 가중치의 합이 최소여야 한다.
2. 사이클이 있으면 안된다(순환X)
3. n개의 정점을 가지는 그래프는 반드시 n-1개의 간선을 사용해야 한다.

MST를 통해 통신망, 도로망, 유통망에서 최소 비용을 찾기 위해 사용하는 알고리즘이다.

MST는 Kruskal과 Prim이 있다. Kruskal은 Greedy를 사용하여 해답을 찾는 방법이다. Prim은 시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해 나가는 방법이다.

자세한 내용은 여기와 여기를 참고하자

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

//CompareTo를 통해 비교할 수 있도록
class Node implements Comparable<Node>{
    int to;
    int value;

    public Node(int to, int value){
        this.to = to;
        this.value = value;
    }

    @Override
    public int compareTo(Node o){
        return this.value - o.value;
    }


}

//1197
public class Main {
    public static boolean[] visited;
    public static int answer = 0;
    //Node타입에 List배열
    //{ArrayList, ArrayList, ArrayList ...} 이런 느낌. 배열 안에 ArrayList구성되어 있음 
    public static List<Node>[] list;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = br.readLine().split(" ");
        int v = Integer.parseInt(arr[0]);
        int e = Integer.parseInt(arr[1]);

        visited = new boolean[v+1];
        //ArrayList배열의 크기 설정
        list = new ArrayList[v+1];

        for(int i=1;i<list.length;i++){
        	//list의 요소들을 ArrayList로 초기화
            list[i] = new ArrayList<>();
        }

        for(int i=0;i<e;i++){
            arr = br.readLine().split(" ");
            int a = Integer.parseInt(arr[0]);
            int b = Integer.parseInt(arr[1]);
            int c = Integer.parseInt(arr[2]);

            list[a].add(new Node(b, c));
            list[b].add(new Node(a, c));
        }

        prim(1);
        System.out.println(answer);

    }

    public static void prim(int start){
    	//우선순위 큐를 통해 최솟값 뽑아내기
        Queue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));

        while(!pq.isEmpty()){
            Node currentNode = pq.poll();
            int to = currentNode.to;
            int value = currentNode.value;

            if(visited[to]) continue;
            visited[to] = true;
            answer += value;

            for(Node node : list[to]){
                if(!visited[node.to]){
                    pq.add(node);
                }
            }

        }
    }

}