[백준] 1197번 - 최소 스패닝 트리 (Gold 4)

문제 링크

백준 1197번 - 최소 스패닝 트리 (Gold 4)

문제 설명

주어진 그래프의 최소 신장 트리의 가중치를 구하는 프로그램을 작성하시오.
최소 신장 트리란 주어진 그래프의 모든 정점을 연결하는 부분 그래프 중 가중치의 합이 최소인 트리이다.

정답 코드 및 설명

백준 1647번 - 도시 분할 계획 (Gold 4)에서 간략하게 설명했듯이, 최소 신장 트리를 구하는 알고리즘은 프림 알고리즘과 크루스칼 알고리즘 두 가지가 대표적으로 알려져 있다.
앞의 문제의 풀이에서 크루스칼 알고리즘을 사용하였으므로, 이 문제는 프림 알고리즘을 사용한 코드를 첨부하였다. 물론 이 문제를 크루스칼 알고리즘으로 풀어도 상관없다.

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 BOJ1197 {
    int v;
    ArrayList<Edge>[] adj;

    static class Edge implements Comparable<Edge> {
        int end, weight;

        Edge(int end, int weight) {
            this.end = end;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge o) {
            if (this.weight > o.weight) return 1;
            if (this.weight < o.weight) return -1;
            return this.end - o.end;
        }
    }

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        v = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());
        adj = new ArrayList[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new ArrayList<>();
        }
        while (e-- > 0) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken()) - 1;
            int end = Integer.parseInt(st.nextToken()) - 1;
            int weight = Integer.parseInt(st.nextToken());
            adj[start].add(new Edge(end, weight));
            adj[end].add(new Edge(start, weight));
        }
    }

    int Prim() {
        int totalWeight = 0;
        boolean[] isSelected = new boolean[v];
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.add(new Edge(0, 0));
        while (!pq.isEmpty()) {
            Edge currEdge = pq.poll();
            int curr = currEdge.end;
            if (isSelected[curr]) continue;
            isSelected[curr] = true;
            totalWeight += currEdge.weight;
            for (Edge e : adj[curr]) {
                if (isSelected[e.end]) continue;
                pq.add(e);
            }
        }
        return totalWeight;
    }

    void solution() throws IOException {
        input();
        System.out.println(Prim());
    }

    public static void main(String[] args) throws IOException {
        new BOJ1197().solution();
    }
}