백준 1647 도시 분할 계획

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

import java.io.*;
import java.util.*;
public class Main {
	static int N, M, Ans;
	static ArrayList<Node>[] list;
	static int[] dist;
	static boolean[] v;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		list = new ArrayList[N+1];
		dist = new int[N+1];
		v = new boolean[N+1];
		for (int i = 1; i < list.length; i++) {
			list[i] = new ArrayList<Node>();
		}
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			list[start].add(new Node(end, weight));
			list[end].add(new Node(start, weight));
		}
		Arrays.fill(dist, Integer.MAX_VALUE);
		dist[1] = 0;
		PriorityQueue<Node> queue = new PriorityQueue<Node>();
		queue.add(new Node(1,  0));
		int sum = 0;
		int max = 0;
		while(!queue.isEmpty()) {
			Node node = queue.poll();
			if(!v[node.end]) {
				v[node.end] = true;
				sum += node.weight;
				max = Math.max(max, node.weight);
				for (Node next : list[node.end]) {
					if(!v[next.end] && dist[next.end] > next.weight) {
						dist[next.end] = next.weight;
						queue.offer(next);
					}
				}
			}
		}
		System.out.println(sum-max);	
	}
	private static class Node implements Comparable<Node>{
		int end, weight;
		public Node( int end, int weight) {
			super();
			this.end = end;
			this.weight = weight;
		}
		@Override
		public int compareTo(Node o) {
			return Integer.compare(this.weight, o.weight);
		}
	}
}

해결방법

다음과 같이 접근하였다.
1. 임의의 두 집 사이에는 경로가 항상 존재해야 한다, 길의 유지비의 합을 최소로 하고싶다.
-> MST 알고리즘 (여기서는 Prim을 사용했다.)
2. 마을을 두 개로 분할해야한다. 각 마을에서만 연결되면 된다.
-> 최소비용으로 만들어야함. -> 가장 비용이 큰 경로를 삭제하여 마을을 나누면 그 것이 최소.
=> MST를 구하고 그 중 가장 큰 비용을 삭제