b1647. 도시 분할 계획

 

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

 

 

 

이 문제는 크루스칼 알고리즘을 사용해 최소 스패닝 트리(MST)를 구하면서

가장 큰 간선 비용을 제외해 두 개의 연결된 부분으로 나누는 문제다.

목표는 모든 정점을 최소 비용으로 연결하는 트리를 구성하되,

가장 큰 비용의 도로를 제외해 두 개의 분리된 부분으로 만드는 것이다.

 

먼저 main 메서드에서 정점 개수 N과 간선 개수 M을 입력받고,

유니온-파인드를 위한 부모 배열 p를 초기화한다.

각 간선의 정보를 입력받아 우선순위 큐 pq에 저장하며,

큐는 간선의 비용을 기준으로 오름차순 정렬된다.

 

calculate 메서드는 크루스칼 알고리즘을 사용해 MST를 구한다.

우선순위 큐에서 가장 작은 간선부터 하나씩 꺼내어,

두 정점이 이미 연결되어 있지 않은 경우 유니온 연산으로 연결한다.

이때 MST의 총 비용을 sum에 더하고, 가장 큰 간선의 비용을 max에 기록한다.

 

마지막으로 MST의 총 비용에서 가장 큰 간선 비용을 뺀 값을 반환해

두 개의 최소 비용 연결 그래프를 만들기 위한 최소 비용을 구한다.

 

 

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

public class Main {

    private static int[] p;
    private static PriorityQueue<int[]> pq;

    private static int find(int a){
        if(p[a] == a) return a;
        else return p[a] = find(p[a]);
    }

    private static void union(int a, int b){
        p[find(a)] = find(b);
    }

    private static int calculate(){
        int max = Integer.MIN_VALUE, sum = 0;

        while(!pq.isEmpty()){
            int[] arr = pq.poll();
            if(find(arr[0]) != find(arr[1])){
                union(arr[0], arr[1]);
                max = Math.max(max, arr[2]);
                sum += arr[2];
            }
        }
        return sum - max;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        p = new int[N+1];
        pq = new PriorityQueue<>(Comparator.comparingInt(o -> o[2]));

        for(int i = 0 ; i < N ; i++){
            p[i] = i;
        }

        for(int i = 0 ; i < M ; i++){
            st = new StringTokenizer(br.readLine());
            int[] arr = {Integer.parseInt(st.nextToken())
                    ,Integer.parseInt(st.nextToken())
                    ,Integer.parseInt(st.nextToken())};
            pq.add(arr);
        }
        System.out.println(calculate());
    }
}