[Java] 백준 21924번 : 도시 건설

1. 문제

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

21924번: 도시 건설

 

 

2. 풀이과정

1. 간선의 개수가 노드 수에 비해 현저히 적으므로, kruskal을 선택했다.

2. cost가 적은 간선부터 탐색하기 위해 PriorityQueue를 사용

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int N, M, p[];
    static long result;
    static PriorityQueue<Edge> edges;

    public static class Edge implements Comparable<Edge>{
        int s, e, c;

        public Edge(int s, int e, int c){
            this.s = s;
            this.e = e;
            this.c = c;
        }

        @Override
        public int compareTo(Edge o) {
            return this.c - o.c;
        }
    }

    public static int find(int n1){
        if(p[n1]==0){
            return n1;
        }
        return p[n1] = find(p[n1]);
    }

    public static boolean union(int n1, int n2){
        n1 = find(n1);
        n2 = find(n2);
        if(n1==n2){return false;}
        p[n2] = n1;
        return true;
    }

    public static void kruskal() {
        int cnt = 0;

        while(!edges.isEmpty()){
            Edge edge = edges.poll();
            if(union(edge.s, edge.e)){
                result -= edge.c;
                if(++cnt == N-1){
                    break;
                }
            }
        }
        if(cnt < N-1){
            result = -1;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        p = new int[N+1];
        edges = new PriorityQueue<>();

        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            edges.add(new Edge(s, e, c));
            result += c;
        }

        kruskal();
        System.out.println(result);

    }
}

 

 

결과