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

문제

www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

풀이

1) Prim-Jarnik 알고리즘

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;
import java.util.StringTokenizer;


class Edge implements Comparable<Edge>{
    int n;
    double d;
    public Edge(int n,int d){
        this.n = n;
        this.d = d;
    }
    @Override
    public int compareTo(Edge comp) {
        return Double.compare(this.d, comp.d);
    }
}
public class Main {
    static ArrayList<ArrayList<Edge>> graph;
    static boolean[] visited;
    static PriorityQueue<Edge> queue;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());
        int answer=0,cnt=0;
        graph = new ArrayList<>();
        visited = new boolean[V+1];

        //그래프 생성
        for(int i=1;i<=V;i++)
            graph.add(new ArrayList<>());
        for(int i=0;i<E;i++){
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken())-1;
            int to = Integer.parseInt(st.nextToken())-1;
            int w = Integer.parseInt(st.nextToken());
            graph.get(from).add(new Edge(to,w));
            graph.get(to).add(new Edge(from,w));
        }
        //계산
        queue = new PriorityQueue<>();
        queue.add(new Edge(0,0));
        while(!queue.isEmpty()){
            Edge tmp = queue.poll();
            if(!visited[tmp.n]){
                visited[tmp.n] = true;
                answer+=tmp.d;
                for(Edge edge : graph.get(tmp.n)){
                    if(!visited[edge.n]){
                        queue.add(edge);
                    }
                }
            }
        }
        System.out.println(answer);
    }

}

2) Kruskal 알고리즘

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;
import java.util.StringTokenizer;


class Edge implements Comparable<Edge>{
    int u,v,w;
    public Edge(int u,int v,int w){
        this.u = u;
        this.v = v;
        this.w = w;
    }
    @Override
    public int compareTo(Edge comp) {
        return Double.compare(this.w, comp.w);
    }
}
public class Main {
    static PriorityQueue<Edge> queue;
    static ArrayList<Edge> T;
    static int[] parent, pcnt;

    static int find(int x){
        if(parent[x] == x)
            return x;
        return parent[x] = find(parent[x]);
    }
    static void union(int x, int y){
        x = find(x);
        y = find(y);
        if(x!=y)
            parent[y] = x;
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());
        int cnt=0;
        parent = new int[V+1];
        pcnt = new int[V+1];
        T = new ArrayList<>();
        queue = new PriorityQueue<>();
        for(int i=1;i<=V;i++){
            parent[i] = i;
            pcnt[i] = 0;
        }

        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 w = Integer.parseInt(st.nextToken());
            queue.add(new Edge(from,to,w));
        }

        //계산
        while(!queue.isEmpty()){
            Edge edge = queue.poll();
            int pu = find(edge.u);
            int pv = find(edge.v);
            if(pu!=pv){
                union(pu,pv);
                cnt+=edge.w;
            }

        }
        System.out.println(cnt);
    }

}