백준 6497 - 전력난

Java

6497 번 - 전력난

문제

모든 두 집 쌍에 대해, 불이 켜진 길만으로 서로를 왕래할 수 있도록 길을 연결해야한다.
최소 비용으로 연결한 후, 절약할 수 있는 최대 액수를 구하시오.

접근 방법

문제는 최소 스패닝 트리(MST)를 구하는 간단한 문제였지만, 문제 입력 조건을 제대로 이해하지 못하여 고생을 한 문제이다.

문제의 조건에 따르면 입력은 여러 개의 테스트 케이스로 구분되어 있다.라고 되어있다.
즉, 테스트 케이스는 여러개이며 이 테스트 케이스의 끝이 주어져 있다.

입력의 끝에서는 첫 줄에 0이 2개 주어진다.이므로, 입력으로 n과 m이 0, 0이 나올 때 까지 테스트 케이스를 while문으로 반복시켜야한다.

코드

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

public class Main {
	static int n, m;
	static long result;
	static int[] parent;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	while(true) {
    		stk = new StringTokenizer(br.readLine());
	    	n = stoi(stk.nextToken());	// 집의 수
	    	m = stoi(stk.nextToken());	// 길의 수
	    	result = 0;
			// n과 m이 0, 0이라면 입력이 종료된다.
	    	if(n == 0 && m == 0)
	    		break;
	    	
	    	parent = new int[n]; 
	    	
	    	PriorityQueue<Road> pq = new PriorityQueue<>((o1, o2)->{return Integer.compare(o1.v, o2.v);});
	    	int from, to, v;
	    	for(int i = 0; i < m; i++) {
	    		stk = new StringTokenizer(br.readLine());
	    		from = stoi(stk.nextToken());
	    		to = stoi(stk.nextToken());
	    		v = stoi(stk.nextToken());;
	    		pq.add(new Road(from,to,v));
	    		result += v;
	    	}
	    	
	    	init();
	    	
	    	Road rd;
	    	int cnt = 0;
	    	long sum = 0;
	    	
	    	while(!pq.isEmpty()) {
	    		rd = pq.poll();
	    		// 간선 연결 개수는 정점의 수 - 1 개
	    		if(cnt == n - 1)
					break;
	    		
	    		if(union(rd.from, rd.to)) {
	    			sum += rd.v;
	    			cnt++;
	    		}
	    	}
	    	
	    	System.out.println(result - sum);
    	}
    	br.close();
	}

	static void init() {
		for(int i = 0; i < n; i++)
			parent[i] = i;
	}
	
	static int findSet(int num) {
		if(num == parent[num])
			return num;
		return parent[num] = findSet(parent[num]);
	}
	
	static boolean union(int a, int b) {
		int aRoot = findSet(a);
		int bRoot = findSet(b);
		if(aRoot == bRoot)
			return false;
		int min = Math.min(aRoot, bRoot);
		parent[aRoot] = min;
		parent[bRoot] = min;
		return true;
	}
	
	static class Road{
		int from, to, v;

		public Road(int from, int to, int v) {
			super();
			this.from = from;
			this.to = to;
			this.v = v;
		}

		@Override
		public String toString() {
			StringBuilder builder = new StringBuilder();
			builder.append("[from=").append(from).append(", to=").append(to).append(", v=").append(v).append("]");
			return builder.toString();
		}
		
	}
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

문제 조건을 잘 읽는다고 해도, 결국 놓치게 된다.
특히 result를 갱신을 안해줘서 더 틀린다.
왠만하면 지역변수로 쓰는게 나을 듯 하다.

개선할 점

없습니다.