[백준 1647 | MST] 도시 분할 계획

 

풀이

이전 포스팅에서 다루었던 최소 스패닝 트리 문제를 아주 간단하게 응용하여 풀 수 있는 문제입니다. 최소 스패닝 트리를 이전과 마찬가지로 구하고 나서, 최소 스패닝 트리를 잇는 가장 가중치가 큰 간선을 제외하면 가장 작은 비용으로 두 마을을 나누어줄 수 있습니다. 따라서 최소 스패닝 트리를 생성할 때에 추가되는 간선의 가중치 중, 가장 큰 값을 저장해두었다가 트리의 생성 비용에서 제거해주면 됩니다.

 

소스 코드(JAVA)

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

public class Kruskal {
    public static int[] parent;
    public static ArrayList<Edge> edgeList;

    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 token = new StringTokenizer(br.readLine());

        int v = Integer.parseInt(token.nextToken());
        int e = Integer.parseInt(token.nextToken());
        parent = new int[v];
        edgeList = new ArrayList<Edge>();

        for(int i=0;i<v;i++) parent[i] = i;
        for(int i=0;i<e;i++){
            token = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(token.nextToken()) - 1;
            int end = Integer.parseInt(token.nextToken()) - 1;
            int val = Integer.parseInt(token.nextToken());
            edgeList.add(new Edge(start, end, val));
        }
        Collections.sort(edgeList);

        long sum = 0;
        long max = 0;
        for(int i=0; i<edgeList.size(); i++){
            Edge edge = edgeList.get(i);
            if(!isSameParent(edge.v1, edge.v2)) {
                sum += edge.cost;
                if(max < edge.cost) max = edge.cost;
                union(edge.v1, edge.v2);
            }
        }

        bw.write((sum - max)+"\n");
        bw.flush();
        bw.close();
    }

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

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

    public static boolean isSameParent(int x, int y) {
        return find(x) == find(y);
    }
}

class Edge implements Comparable<Edge> {
    int v1, v2, cost;
    Edge(int v1, int v2, int cost) {
        this.v1 = v1;
        this.v2 = v2;
        this.cost = cost;
    }

    @Override
    public int compareTo(Edge o) {
        if (this.cost < o.cost) return -1;
        else if(this.cost == o.cost) return 0;
        else return 1;
    }
}