[백준] 1196 최소 스패닝 트리 - 자바

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

1197번: 최소 스패닝 트리

문제 풀이

최소 스패닝 트리(MST)를 구하는 알고리즘으로 크루스칼, 프림이 있다. 두 알고리즘 모두 연습할 겸 두 가지 방법 모두 사용해 보았다.

자세한 이론은 생략하고 두 알고리즘을 간단하게 비교한 표를 살펴보자.

최소 신장 트리 (MST)	탐색 순서	방문 체크	비고
크루스칼(Kruskal)	최소 비용 간선부터 시작	union-find
프림(Prim)	임의 정점에서 최소 비용 간선을 갖는 인접 정점부터 시작	visited[]	최소 간선을 갖는 인접 노드를 다루기 위해 Priority Queue 사용

코드 - Kruskal

package 백준;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Edge{
    int from;
    int to;
    int cost;

    public Edge(int from, int to, int cost) {
        this.from = from;
        this.to = to;
        this.cost = cost;
    }
}

public class b1197_Kruskal {
    static Edge[] edges;
    static int[] parent;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());

        edges = new Edge[E];
        parent = new int[V + 1];
        for (int i = 0; i < V + 1; i++) {
            parent[i] = i;
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            edges[i] = new Edge(from, to, cost);
        }

        Arrays.sort(edges, (e1, e2) -> e1.cost - e2.cost);

        int weight = 0; // 가중치
        int mstEdges = 0; // 최소스패닝트리의 간선 갯수
        for (int i = 0; i < E; i++) {
            Edge edge = edges[i];
            int from = edge.from;
            int to = edge.to;
            int cost = edge.cost;

            if (union(from, to)) {
                weight += cost;
                mstEdges++;

                if (mstEdges == E - 1) {
                    break;
                }
            }
        }

        System.out.println(weight);
    }

    static boolean union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);

        if (rootA == rootB)
            return false;

        parent[rootB] = rootA;
        return true;
    }

    static int find(int n) {
        if (parent[n] != n)
            parent[n] = find(parent[n]);

        return parent[n];
    }
}

 

코드 - Prim

package 백준;

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

class Node{
    int idx;
    int cost;

    public Node(int idx, int cost) {
        this.idx = idx;
        this.cost = cost;
    }
}

public class b1197_Prim {
    static int V, E;
    static List<Node>[] tree;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        tree = new ArrayList[V + 1];
        for (int i = 1; i < V + 1; i++) {
            tree[i] = new ArrayList<>();
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            tree[from].add(new Node(to, cost));
            tree[to].add(new Node(from, cost));
        }

        System.out.println(prim());
    }

    static int prim() {
        int weight = 0;
        visited = new boolean[V + 1];

        Queue<Node> pq = new PriorityQueue<>((n1, n2) -> n1.cost - n2.cost);
        pq.offer(new Node(1, 0));  // 임의의 간선부터 시작

        while (!pq.isEmpty()) {
            Node now = pq.poll();
            int idx = now.idx;
            int cost = now.cost;

            if (visited[idx]) continue;
            // MST 간선 추가
            visited[idx] = true;
            weight += cost;

            for (Node adj : tree[idx]) {
                if (!visited[adj.idx])
                    pq.offer(adj);
            }
        }

        return weight;
    }
}