백준 6497 전력난 java

문제로이동

---

목차

 

---

---

문제 설명

일반적인 최소스패닝 트리(MST) 문제입니다.

크루스칼 알고리즘과 프림 알고리즘으로 해결해봤습니다.

 

---

런타임 에러1

이 문제는 테스트 케이스가 여러개 들어옵니다. 마지막 0 0 입력이 왜 있는가 했더니,,

결국 이 문제점을 뒤늦게 이해하고 코드 수정을 하여 AC를 받았습니다.

즉, 0 0이 입력되기 전까지 테스트 케이스가 무한대로 들어오니 M,N 값을 검증해야 합니다.

 

if(M==0 && N==0)
	return;

---

런타임 에러2

전혀 생각지 못했던 이유였습니다.

하단 소스코드엔 while문 밖으로 선언되어 있지만 아래처럼 while문 내에 삽입했더니 발생했습니다.

 

while(true){
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    //Your Code
}

 

위와 같이 BufferedReader 선언을 반복문 내에 넣었더니 계속해서 ArrayIndexOutOfBounds가 발생합니다.

늘 새로운 상황의 에러가 저를 반겨주니 감개무량하네요.

이 에러도 정확한 원인을 파악해보고 수정하도록 하겠습니다.

---

소스 코드

Java8 크루스칼

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

public class Main_kruskal {
	static StringBuilder sb = new StringBuilder();
	static int N,M,parent[];
	static int getParent(int x) {
		if(parent[x] == x)return x;
		return parent[x] = getParent(parent[x]);
	}
	static void unionParent(int a,int b) {
		a = getParent(a);
		b = getParent(b);
		if(a<b)parent[b]=a;
		else parent[a]=b;
	}
	static void input() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		while(true) {
			st = new StringTokenizer(br.readLine());
			M = Integer.parseInt(st.nextToken());//집의수
			N = Integer.parseInt(st.nextToken());//길의수
			if(M==0 && N==0)break;
			parent = new int[M];
			for(int i =0;i<M;i++)parent[i]=i;
			class Edge{
				int from,to,dist;
				public Edge(int from, int to, int dist) {this.from = from;this.to = to;this.dist = dist;}			
			}
			ArrayList<Edge> query = new ArrayList<>();
			int total = 0;
			for(int i=0;i<N;i++) {//길의 정보
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				int d = Integer.parseInt(st.nextToken());
				total+=d;
				query.add(new Edge(a,b,d));
			}
			Collections.sort(query,(o1,o2)->o1.dist-o2.dist);
			int answer =0;
			for(Edge edge:query) {
				int a = edge.from;
				int b = edge.to;
				if(getParent(a)==getParent(b))continue;
				unionParent(a,b);
				answer+=edge.dist;
			}
			sb.append(total-answer).append("\n");
		}		
	}

	public static void main(String[] args) throws IOException {
		input();
		System.out.println(sb);
	}
}

---

Java8 프림

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

public class Main_Prim {
	static StringBuilder sb = new StringBuilder();
	static int N,M;
	static boolean visited[];
	static class Edge implements Comparable<Edge>{
		int node,dist;
		public Edge(int node, int dist) {this.node = node;this.dist = dist;}
		@Override
		public int compareTo(Edge o) {			
			return this.dist-o.dist;
		}		
	}
	static void input() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		while(true) {
			st = new StringTokenizer(br.readLine());
			M = Integer.parseInt(st.nextToken());//집의수
			N = Integer.parseInt(st.nextToken());//길의수
			if(M==0 && N==0)break;
			visited = new boolean[M];
			ArrayList<ArrayList<Edge>> query = new ArrayList<>();
			for(int i =0;i<M;i++)query.add(new ArrayList<>());
			int totalCost = 0;
			for(int i=0;i<N;i++) {//길의 정보
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				int d = Integer.parseInt(st.nextToken());
				totalCost+=d;
				query.get(a).add(new Edge(b,d));
				query.get(b).add(new Edge(a,d));
			}
			PriorityQueue<Edge> pq = new PriorityQueue<>();
			for(Edge cur:query.get(0))
				pq.add(cur);//임의의 정점 0부터 시작한다.
			visited[0]=true;
			int minCost =0;
			while(!pq.isEmpty()) {
				Edge edge = pq.poll();
				if(visited[edge.node])continue;//이미 방문했다면
				visited[edge.node]=true;				
				minCost+=edge.dist;				
				for(Edge next:query.get(edge.node)) {
					pq.add(next);//다음 pq에 추가
				}
			}
			sb.append(totalCost-minCost).append("\n");
		}		
	}

	public static void main(String[] args) throws IOException {
		input();
		System.out.println(sb);
	}
}