[백준 21924] 도시건설 (JAVA)

백준(BOJ) 21924 도시건설

 

난이도
230528 기준 골드 4

사용 알고리즘
최소스패닝트리(크루스칼)

문제 링크
https://www.acmicpc.net/problem/21924

21924번: 도시 건설

 

풀이 과정

 

1. 문제 읽기(중요한 부분 굵은 표시)

(문제에 그림이 있으니 백준 가셔서 보세요)

 

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

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

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

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

 

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

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

 

입력

 

출력

 

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

 

 

2. 어떤 알고리즘을 사용할 것인가

 

 도로를 간선이라 생각하고 도로 비용이 낮은 순으로 하나씩 뽑으면서 크루스칼을 하면 금방 풀릴 것 같습니다.

 

 

3. 풀이 구상

 

 Edge 클래스를 만들고 length가 낮은 순으로 PriorityQueue에 넣어줍니다. 그리고 크루스칼 알고리즘을 사용하면 됩니다. 비용 낮은 Edge 뽑고 사이클이면 반영안하고 사이클 아니면 반영시키고 그런식으로 N-1개 까지 뽑아보고 N-1개가 안뽑혀서 모든 건물이 연결되지 않으면 -1을 출력해줍니다. 그리고 출력조건에 얼마나 절약 할 수 있는지를 출력하라 나와있으니 미리 모든 도로의 비용을 더해놓고 MST의 비용의 합을 뺀 것을 출력하는 것만 조심하면 무난히 풀리겠네요

 

 

4. 코드 작성

 

1. 정답 코드

 

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

public class Main {

    static int N, M;

    static long total, selTotal;

    static PriorityQueue<Edge> pq;

    static int[] repArr;

    static class Edge implements Comparable<Edge> {
        int left;
        int right;
        int length;

        public Edge(int left, int right, int length) {
            this.left = left;
            this.right = right;
            this.length = length;
        }

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

    public static void main(String[] args) throws IOException {


        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        total = 0;
        selTotal = 0;
        repArr = new int[N + 1];
        for (int i = 0; i <= N; i++) {
            repArr[i] = i;
        }

        pq = new PriorityQueue<>();

        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            total += c;
            pq.offer(new Edge(a, b, c));
        }

        if (doKruskal()) {
            bw.write((total - selTotal) + "");
        } else {
            bw.write("-1");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    private static boolean doKruskal() {

        int selectedCnt = 0;

        while (pq.size() > 0) {
            Edge poll = pq.poll();

            int pl = poll.left;
            int pr = poll.right;

            if (merged(pl, pr)) {
                selTotal += poll.length;
                selectedCnt++;
                if (selectedCnt == N - 1) {
                    return true;
                }
            }
        }
        return false;
    }

    private static boolean merged(int pl, int pr) {
        if (findParent(pl) == findParent(pr)) {
            return false;
        } else {
            repArr[findParent(pl)] = findParent(pr);
            return true;
        }
    }

    private static int findParent(int child) {
        if (repArr[child] == child) {
            return child;
        } else {
            return repArr[child] = findParent(repArr[child]);
        }
    }
}

 

 

---

풀이 후기

  MST 문제는 크루스칼로 풀지 프림으로 풀지만 정하면 무난히 풀립니다. 대신 크루스칼과 프림을 어떻게 쓰는지 정확히 알아야겠죠? 까먹지 않게 주기적으로 한 문제씩 풀어주는건 좋은 것 같습니다.