[BOJ] 백준 6497 : 전력난 (java)

🧪 6497 전력난

---

난이도 : 🌟 골드 4
유형 : 크루스칼 알고리즘

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

 

📝 문제

---

성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들어가는데, 일부를 소등하여 그만큼의 돈을 절약할 수 있다.

그러나 만약 어떤 두 집을 왕래할 때, 불이 켜져 있지 않은 길을 반드시 지나야 한다면 위험하다. 그래서 도시에 있는 모든 두 집 쌍에 대해, 불이 켜진 길만으로 서로를 왕래할 수 있어야 한다.

위 조건을 지키면서 절약할 수 있는 최대 액수를 구하시오.

 

입력

 

입력은 여러 개의 테스트 케이스로 구분되어 있다.

각 테스트 케이스의 첫째 줄에는 집의 수 m과 길의 수 n이 주어진다. (1 ≤ m ≤ 200000, m-1 ≤ n ≤ 200000)

이어서 n개의 줄에 각 길에 대한 정보 x, y, z가 주어지는데, 이는 x번 집과 y번 집 사이에 양방향 도로가 있으며 그 거리가 z미터라는 뜻이다. (0 ≤ x, y < m, x ≠ y)

도시는 항상 연결 그래프의 형태이고(즉, 어떤 두 집을 골라도 서로 왕래할 수 있는 경로가 있다), 도시상의 모든 길의 거리 합은 231미터보다 작다.

입력의 끝에서는 첫 줄에 0이 2개 주어진다.

 

출력

 

각 테스트 케이스마다 한 줄에 걸쳐 절약할 수 있는 최대 비용을 출력한다.

 

🚧  주의할 점

---

1. 입력이 여러개의 테스트 케이스로 구분되어 있다고 했고, 입력의 끝이 0, 0이라고 나와있기 때문에 while문을 통해서 반복을 해주고 변수들을 초기화 해줘야 한다.

🧐 핵심 로직 

---

1) 여러개의 테스트 케이스를 받기 위한 while문 내부에서 입력값을 받아준다.

 

2) 사용하는 액수가 아닌 절약 액수이기 때문에 res 변수에 미리 모든 액수를 담아둔다.

 

3) 모든 간선에 대한 정보를 graph변수에 넣어주고 오름차순으로 정렬해준다.

 

4) 유니온-파인드 구조를 활용하여 최소 신장 트리를 완성하고 res 변수에 저장해둔 액수에서 사용한 액수를 빼준 절약 액수를 출력한다.

 

💻 최종 코드 (928 ms)

---

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

public class Main {

    static class Node implements Comparable<Node> {
        int start, end, dist;

        Node(int start, int end, int dist) {
            this.start = start;
            this.end = end;
            this.dist = dist;
        }

        @Override
        public int compareTo(Node o) {
            return this.dist - o.dist;
        }
    }

    static int m, n, res;
    static int[] parent;
    static List<Node> graph;
    public static void main(String[] args) throws IOException {

        // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("input.txt"));

        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            m = Integer.parseInt(st.nextToken());
            n = Integer.parseInt(st.nextToken());
            res = 0;

            if (m == 0 && n == 0) {
                br.close();
                return;
            }

            graph = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                int start = Integer.parseInt(st.nextToken());
                int end = Integer.parseInt(st.nextToken());
                int dist = Integer.parseInt(st.nextToken());

                graph.add(new Node(start, end, dist));
                res += dist;
            }

            parent = new int[m];
            for (int i = 0; i < m; i++) {
                parent[i] = i;
            }

            Collections.sort(graph);

            for (Node curNode : graph) {
                if (find(curNode.start) != find(curNode.end)) {
                    union(curNode.start, curNode.end);

                    res -= curNode.dist;
                }
            }

            System.out.println(res);
        }
    }

    public static void union(int x, int y) {
        x = find(x);
        y = find(y);

        if (x != y) {
            parent[y] = x;
        }
    }

    private static int find(int x) {
        if (x == parent[x]) {
            return x;
        }

        return parent[x] = find(parent[x]);
    }
}