[백준 P21924] 도시 건설 Java

P21924 도시 건설

21924번: 도시 건설

 

문제

채완이는 신도시에 건물 사이를 잇는 양방향 도로를 만들려는 공사 계획을 세웠다.

공사 계획을 검토하면서 비용이 생각보다 많이 드는 것을 확인했다.

채완이는 공사하는 데 드는 비용을 아끼려고 한다.

모든 건물이 도로를 통해 연결되도록 최소한의 도로를 만들려고 한다.

 

위 그림에서 건물과 직선으로 표시된 도로, 해당 도로를 만들 때 드는 비용을 표시해놓은 지도이다.

그림에 있는 도로를 다 설치할 때 드는 비용은 62이다. 모든 건물을 연결하는 도로만 만드는 비용은 27로 절약하는 비용은 35이다.

채완이는 도로가 너무 많아 절약되는 금액을 계산하는 데 어려움을 겪고 있다.

채완이를 대신해 얼마나 절약이 되는지 계산해주자.

 

입력값

7 9
1 2 15
2 3 7
1 3 3
1 4 8
3 5 6
4 5 4
4 6 12
5 7 1
6 7 6

8 10
1 2 4
2 3 9
2 4 9
3 4 4
3 5 1
4 6 14
6 7 5
5 7 3
7 8 7
6 8 3

5 4
1 2 1
2 3 1
3 1 1
4 5 5

 

출력값

예산을 얼마나 절약 할 수 있는지 출력한다. 만약 모든 건물이 연결되어 있지 않는다면 -1을 출력한다.

35

30

-1

 

알고리즘

모든 도로를 다 설치하는 경우와 모든 건물을 연결하는 최소한의 도로만 설치하는 경우를 각각 구해서 차를 구하면 해결할 수 있는 문제이다.

 

모든 도로를 다 구하는 것은 간선의 정보를 입력받으면서 가중치를 모두 더하면서 해결할 수 있었다. 모든 건물을 연결하는 최소한의 도로를 설치하는 경우를 구해야 한다. MST를 사용하면 모든 정점을 연결할 때 쓰이는 최소 비용을 구할 수 있다.

 

이 문제는 간선의 정보가 주어지기에, 프림보다는 크루스칼 알고리즘을 사용하는 것이 더 좋다고 판단했다. 프림은 정점을 기준으로 MST를 구성하는 반면 크루스칼은 간선을 기준으로 MST를 구성한다. 간선의 정보가 입력으로 들어오는만큼 크루스칼을 사용하는 것이 좋다고 판단했다.

 

크루스칼을 사용하기 위해 union, find 메서드를 각각 구현했고, PriorityQueue 자료구조를 이용해서 현재까지 탐색하지 않은 간선들 중 가장 작은 가중치를 가지는 간선을 뽑아냈다.

 

그렇게 크루스칼 알고리즘을 사용해서 모든 정점을 연결할 수 있다면, 인풋을 입력받으며 계산해뒀던 모든 도로를 연결할 때의 가중치에서 MST가 구성되었을때의 가중치를 빼 결과를 구했다.

 

만약 MST가 구성되지 않는다면 모든 건물이 연결되지 않는다는 것이므로 -1을 출력했다.

 

전체 코드는 아래와 같다.

 

코드

import java.util.*;
import java.io.*;

public class Main {
    static int N, M;
    static int[] parent;
    static long originalWeight;
    static long newWeight;
    static PriorityQueue<int[]> edges = new PriorityQueue<>((a, b) -> {
        return a[2] - b[2];
    });

    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());

        parent = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }

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

            edges.add(new int[] {from ,to, weight});
            originalWeight += weight;
        }

        int cnt = 0;
        while (!edges.isEmpty()) {
            int[] current = edges.poll();
            int from = current[0];
            int to = current[1];
            int weight = current[2];

            if (find(from) != find(to)) {

                newWeight += weight;
                union(from, to);
                cnt++;

                if (cnt == N - 1) break;
            }
        }

        if (cnt != N - 1) System.out.println(-1);
        else System.out.println(originalWeight - newWeight);
    }

    public static void union(int a, int b){
        int aParent = find(a);
        int bParent = find(b);

        if (aParent < bParent) {
            parent[bParent] = aParent;
        } else if (bParent < aParent) {
            parent[aParent] = bParent;
        }
    }

    public static int find(int target) {
        if (parent[target] == target) return target;
        else return parent[target] = find(parent[target]);
    }
}