[Algorithm/Java][백준] 1197번 최소 스패닝 트리

[BOJ] 1197번 최소 스패닝 트리

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

문제 접근

모든 정점을 최소 값으로 순회할 수 있는 트리를 구하는 문제이다.
대표적으로 Kruskal과 Prim 알고리즘이 있기 때문에 두 알고리즘을 이용해서 구현하였다.

Code

Kruskal 알고리즘

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
class Edge implements Comparable<Edge> {
    int from;
    int to;
    int cost;

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

    @Override
    public int compareTo(Edge o) {
        return cost - o.cost;
    }
}
public class BOJ1197_kruskal {
    static int V;
    static int E;
    static Edge[] pq;
    static int[] root;
    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());
        root = new int[V + 1];
        pq = new Edge[E];
        for(int i = 0; i <= V; i++){
            root[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());
            pq[i] = new Edge(from, to, cost);
        }
        System.out.println(kruskal());
    }
    public static int kruskal(){
        int sum = 0;
        int cnt = 0;
        Arrays.sort(pq);
        for (Edge edge : pq) {
            if(union(edge.from, edge.to)){
                sum += edge.cost;
                if(++cnt == V - 1) return sum;
            }
        }
        return sum;
    }
    public static boolean union(int a, int b){
        a = find(a);
        b = find(b);
        if(a == b) return false;
        root[a] = b;
        return true;
    }
    public static int find(int a){
        if(root[a] == a) return a;
        else {
            return root[a] = find(root[a]);
        }

    }
}

Prim 알고리즘

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_prime {
    static class Node implements Comparable<Node>{
        int to,cost;

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

        @Override
        public int compareTo(Node o) {
            return cost - o.cost;
        }
    }
    static int V,E;
    static ArrayList<Node>[] adjList; // 인접리스트
    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());
        adjList = new ArrayList[V + 1];
        for(int i = 1; i<=V; i++){
            adjList[i] = new ArrayList<>();
        }
        visited = new boolean[V + 1];
        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());
            adjList[from].add(new Node(to, cost));
            adjList[to].add(new Node(from, cost));
        }
        System.out.println(prim());
    }
    public static int prim(){
        int sum = 0;
        int cnt = 0;
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(1, 0));
        while (!pq.isEmpty()) {
            Node cur = pq.poll();
            if(visited[cur.to]) continue;
            sum += cur.cost;
            visited[cur.to] = true;
            if(++cnt == V) return sum;
            for(Node n : adjList[cur.to]){
                if(visited[n.to]) continue;
                pq.add(n);
            }
        }
        return sum;
    }
}