백준 21924 - 도시 건설

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

21924번: 도시 건설

문제 설명 

채완이는 신도시에 건물 사이를 잇는 양방향 도로를 만들려는 공사 계획을 세웠다.

공사 계획을 검토하면서 비용이 생각보다 많이 드는 것을 확인했다.

채완이는 공사하는 데 드는 비용을 아끼려고 한다. 

모든 건물이 도로를 통해 연결되도록 최소한의 도로를 만들려고 한다.

위 그림에서 건물과 직선으로 표시된 도로, 해당 도로를 만들 때 드는 비용을 표시해놓은 지도이다.

그림에 있는 도로를 다 설치할 때 드는 비용은 62이다. 모든 건물을 연결하는 도로만 만드는 비용은 27로 절약하는 비용은 35이다.

채완이는 도로가 너무 많아 절약되는 금액을 계산하는 데 어려움을 겪고 있다.

채완이를 대신해 얼마나 절약이 되는지 계산해주자.

 

문제 풀이

최소 스패닝 트리(MST) 문제이다. 모든 도로에 대한 거리를 구한 후, 최소 스패닝 트리로 구한 값을 빼주면 절약하는 비용이 나오기 때문에 Prim을 사용하여 최소 스패닝 거리를 구한 후 값을 빼주었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	public static class Node implements Comparable<Node>{
		int node;
		long weight;
		@Override
		public String toString() {
			return "Node [node=" + node + ", weight=" + weight + "]";
		}
		public Node(int node, long weight) {
			this.node = node;
			this.weight = weight;
		}
		@Override
		public int compareTo(Node o) {
			// TODO Auto-generated method stub
			//return Long.compare(this.weight,  o.weight);
			return this.weight<o.weight?-1:1;
		}
	}
	static int N,M;
	static List<Node>[] list;
	static PriorityQueue<Node> pq = new PriorityQueue<>();
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		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 List[N+1];
		boolean[] visited = new boolean[N+1];
		for(int i=0; i<N+1; i++) {
			list[i] = new ArrayList<>();
		}
		long sum1=0;
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			
			int to = Integer.parseInt(st.nextToken());
			int from = Integer.parseInt(st.nextToken());
			long weight = Long.parseLong(st.nextToken());
			
			list[to].add(new Node(from,weight));
			list[from].add(new Node(to,weight));
			sum1+=weight;
		}
		
		long sum = 0;
		pq.add(new Node(1,0));
		while(!pq.isEmpty()) {
			Node temp = pq.poll();
			if(visited[temp.node]) continue;
			int to = temp.node;
			long weight = temp.weight;
			
			visited[to] = true;
			sum+=weight;
			for(Node next : list[to]) {
				if(!visited[next.node]) {
					pq.add(next);
				}
			}
		}
		int cnt=0;
		for(int i=0; i<N+1; i++) {
			if(!visited[i]) cnt++;
		}
		if(cnt>1) {
			System.out.println(-1);
		}
		else {
			System.out.println(sum1-sum);
		}
	}

}