[알고리즘] 백준 > #1647. 도시 분할 계획

문제링크

백준 #1647. 도시 분할 계획

풀이방법

최소 비용을 구해야하고, 두 마을로 구성해야 하기 때문에 Greedy + Union Find 로 해결할 수 있다고 생각했다! 모든 길이 없는 상태(모두 다른 마을)에서 비용이 작은 길부터 확인을 진행했다. 만약 두 집이 다른 마을에 있다면 길을 추가해 같은 마을로 만들고 cost를 더했다! 그렇게 진행하닥 두 마을만 남을 때의 cost를 리턴했다. 길의 비용을 오름차순으로 가져오는 부분은 PriorityQueue를 이용했다. 끝!

코드

class Solution1647 {
    int n, m;
    PriorityQueue<Road> q = new PriorityQueue<>();

    int[] tree;

    final int ROOT = -1;

    Solution1647(int n, int m, LinkedList<Road> edges) {
        this.n = n;
        this.m = m;
        q.addAll(edges);

        initTree();
    }

    int getMinCost() {
        int numOfTown = n;
        int cost = 0;

        while (!q.isEmpty()) {
            Road head = q.poll();

            if (merge(head.houseA, head.houseB)) {
                numOfTown--;
                cost += head.cost;
            }
            if (numOfTown == 2) break;
        }

        return cost;
    }

    private void initTree() {
        tree = new int[n + 1];
        for (int i = 1; i <= n; i++) tree[i] = ROOT;
    }

    private int find(int house) {
        if (tree[house] == ROOT) return house;
        else {
            tree[house] = find(tree[house]);
            return tree[house];
        }
    }

    private boolean merge(int houseA, int houseB) {
        int rootA = find(houseA);
        int rootB = find(houseB);

        if (rootA != rootB) {
            tree[rootA] = rootB;
            return true;
        } else return false;
    }
}

class Road implements Comparable<Road> {
    int houseA;
    int houseB;
    int cost;

    Road(int houseA, int houseB, int cost) {
        this.houseA = houseA;
        this.houseB = houseB;
        this.cost = cost;
    }

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