백준 1647 [자바] java 도시 분할 계획

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

1647번: 도시 분할 계획

 

▶문제

동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다.

마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다.

마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다.

그렇게 마을의 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 되었다. 일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다. 이것을 구하는 프로그램을 작성하시오.

---

▶입력

첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집과 B번 집을 연결하는 길의 유지비가 C (1 ≤ C ≤ 1,000)라는 뜻이다.

---

▶출력

첫째 줄에 없애고 남은 길 유지비의 합의 최솟값을 출력한다.

---

▶해설

한 마을에 있던 집들을 잇는 길과 비용이 제시됩니다. 이때 마을 이장은 두 마을로 분리하며 적어도 마을에는 한 집 이상은 존재해야 합니다. 또한 모든 집들은 최소 비용으로 연결되어야 한다는 조건이 있습니다. 최소 스패닝 트리의 알고리즘을 적용하면 됩니다. 하지만 두 마을로 분리해야 한다는 조건이 있습니다. 이 조건은 매우 쉽게 해결이 가능합니다. 최소 스패닝 트리 특성상 가장 작은 비용이 드는 것을 먼저 연결합니다. 마지막에 연결한 요소가 가장 큰 비용이 드는 길이라는 것을 알 수 있습니다. 최소 스패닝 트리를 연결한 후 마지막의 비용을 빼주면 답이 됩니다.

 

1. 최소 스패닝 트리 완성

2. 마지막 값을 빼준다.

3. find(): 부모를 찾아주는 함수

4. isParent(): 부모가 같은지 확인하는 함수

5. union(): 부모를 같게 해주는 함수

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class node implements Comparable<node> {
    int start;
    int end;
    int cost;

    public node(int start, int end, int cost) {
        this.start = start;
        this.end = end;
        this.cost = cost;
    }

    @Override
    public int compareTo(node o) {
        return this.cost - o.cost;
    }
}

public class Main {
    static int n, m;
    static int[] parent;
    static long result;
    static int max;
    static PriorityQueue<node> queue = new PriorityQueue<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);

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

        for (int i = 0; i < m; i++) {
            String[] s1 = br.readLine().split(" ");
            int start = Integer.parseInt(s1[0]);
            int end = Integer.parseInt(s1[1]);
            int cost = Integer.parseInt(s1[2]);
            queue.add(new node(start, end, cost));
        }

        while (!queue.isEmpty()) {
            node poll = queue.poll();
            if (!isParent(poll.start, poll.end)) {
                union(poll.start, poll.end);
                result += poll.cost;
                max = poll.cost;
            }
        }
        System.out.println(result - max);
    }

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

    public static boolean isParent(int x, int y) {
        int xp = find(x);
        int yp = find(y);
        if (xp != yp) {
            return false;
        } else {
            return true;
        }
    }

    public static void union(int x, int y) {
        int xp = find(x);
        int yp = find(y);
        parent[yp] = xp;
    }
}

최소 스패닝 트리는 find()와 union()의 함수를 이해한다면 쉽게 풀 수 있습니다. 해당 유형이 잘나오는 기업의 코테라면 외워서 가는 것도 하나의 좋은 방법인 거 같습니다!!