원더랜드(최소스패닝트리 : 프림, PriorityQueue)

최소 스패닝 트리 만드는 방법에는 크루스칼 뿐만아니라 프림 알고리즘도 있습니다.

크루스칼 알고리즘을 Union&Find로 구현하였다면 프림 알고리즘은 PriorityQueue를 사용해서 구현합니다.

 

(직전에 풀었던) 같은 문제를 프림 알고리즘을 통해 구현해보도록 하겠습니다.

 

---

 

설명

원더랜드에 문제가 생겼다. 원더랜드의 각 도로를 유지 보수하는 재정이 바닥난 것이다.

원더랜드는 모든 도시를 서로 연결하면서 최소의 유지비용이 들도록 도로를 선택하고 나머지 도로는 폐쇄하려고 한다.

아래의 그림은 그 한 예를 설명하는 그림이다.

위의 지도는 각 도시가 1부터 9로 표현되었고, 지도의 오른쪽은 최소비용 196으로 모든 도시를 연결하는 방법을 찾아낸 것이다.

 

입력

첫째 줄에 도시의 개수 V(1≤V≤100)와 도로의 개수 E(1≤E≤1,000)가 주어진다.

다음 E개의 줄에는 각 도로에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다.

이는 A번 도시와 B번 도시가 유지비용이 C인 도로로 연결되어 있다는 의미이다.

 

출력

모든 도시를 연결하면서 드는 최소비용을 출려한다.

예시 입력 1 

9 12
1 2 12
1 9 25
2 3 10
2 8 17
2 9 8
3 4 18
3 7 55
4 5 44
5 6 60
5 7 38
7 8 35
8 9 15

예시 출력 1

196

 

문제 이해

 

참고 

인접리스트, 배열 안의 배열과 같은 개념이 익숙하지 않다면 이전 발행 글을 참고한 후 다시 풀어보는 것을 권장합니다.

[코딩 테스트(JAVA)/인프런 문제] - 다익스트라 알고리즘(수정 중1)

 

 

수도 코드 & 실패코드(Runtime Error)

package ch09;

import java.util.*;

// 정점, 비용 담을 객체생성
class Line implements Comparable<Line> {
	public int point;
	public int cost;
	
	// 매개변수 있는 생성자
	Line(int point, int cost) {
		this.point = point;
		this.cost = cost;
	}
	
	// cost 오름차순 정렬
	@Override
	public int compareTo(Line e) {
		return this.cost - e.cost;
	}
	
}

public class Wonder2 {
	public static void main(String[] args) {
		// 입력
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int m = kb.nextInt();
		// [배열 안의 배열] a배열을 만들고 a배열 안에 b,c 입력받기
		// a배열 생성 전 빈 껍데기인 graph생성
		ArrayList<ArrayList<Line>> graph = new ArrayList<>();
		// n을 돌면서 a배열 안의 배열 생성
		for(int i=0; i<n; i++) {
			graph.add(new ArrayList<Line>());
		}
		for(int i=0; i<m; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			int c = kb.nextInt();
			// 무방향 인접리스트
			graph.get(a).add(new Line(b,c));
			graph.get(b).add(new Line(a,c));
		}
		// 체크리스트 생성(기본값 0으로 초기화)
		int[] chArr = new int[n];
		
		// 출력관련 코드 시작
		int answer = 0;
		// 우선순위 큐 생성
		PriorityQueue<Line> pQ = new PriorityQueue<>();
		// 출발 : (임의의 점, 주로)첫번째 정점 offer
		pQ.offer(new Line(1,0));
		while(!pQ.isEmpty()) {
			// 임시저장 tmp생성
			Line tmp = pQ.poll();
			// poll한 정점이 체크배열 0이면, cost를 answer+=
			if(chArr[tmp.point] == 0) {
				answer += tmp.cost;
				chArr[tmp.point] = 1;
				// 연결된 간선 정보 pQ에 넣기
				// !![a 접근 방법]!! graph.get(tmp.point)
				for(Line ob : graph.get(tmp.point)) {
					if(chArr[ob.point] == 0) {
						// pQ에 offer
						pQ.offer(new Line(ob.point, ob.cost));
					}
				}
			}
			
		}
	
		System.out.println(answer);
		
	}

}

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 9 out of bounds for length 9

리스트와 같은 자료형에서 인덱스의 범위를 벗어나는 경우 발생하는 에러코드입니다.

 

원인

		// n을 돌면서 a배열 안의 배열 생성 : 0 ~ n-1
		for(int i=0; i<n; i++) {
			graph.add(new ArrayList<Line>());
		}
        
		for(int i=0; i<m; i++) { // 입력 받는 것을 보면 0이 아닌 1부터 시작!
			int a = kb.nextInt();
			int b = kb.nextInt();
			int c = kb.nextInt();
			// 무방향 인접리스트
			graph.get(a).add(new Line(b,c));
			graph.get(b).add(new Line(a,c));
		}
		// 체크리스트 생성(기본값 0으로 초기화) : 0 ~ n-1
		int[] chArr = new int[n];

입력 자체를 0이 아닌 1부터 시작하므로 해당 부분 코드를 수정해주었더니 통과하였습니다!

 

 

성공 코드

package ch09;

import java.util.*;

// 정점, 비용 담을 객체생성
class Line implements Comparable<Line> {
	public int point;
	public int cost;
	
	// 매개변수 있는 생성자
	Line(int point, int cost) {
		this.point = point;
		this.cost = cost;
	}
	
	// cost 오름차순 정렬
	@Override
	public int compareTo(Line e) {
		return this.cost - e.cost;
	}
	
}

public class Wonder2 {
	public static void main(String[] args) {
		// 입력
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int m = kb.nextInt();
		// [배열안의배열] a배열을 만들고 a배열 안에 b,c 입력받기
		// a배열 생성 전 빈 껍데기인 graph생성
		ArrayList<ArrayList<Line>> graph = new ArrayList<>();
		// n을 돌면서 a배열 안의 배열 생성
		for(int i=0; i<=n; i++) {
			graph.add(new ArrayList<Line>());
		}
		for(int i=0; i<m; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			int c = kb.nextInt();
			// 무방향 인접리스트
			graph.get(a).add(new Line(b,c));
			graph.get(b).add(new Line(a,c));
		}
		// 체크리스트 생성(기본값 0으로 초기화)
		int[] chArr = new int[n+1];
		
		// 출력관련 코드 시작
		int answer = 0;
		// 우선순위 큐 생성
		PriorityQueue<Line> pQ = new PriorityQueue<>();
		// 출발 : (임의의 점, 주로)첫번째 정점 offer
		pQ.offer(new Line(1,0));
		while(!pQ.isEmpty()) {
			// 임시저장 tmp생성
			Line tmp = pQ.poll();
			// poll한 정점이 체크배열 0이면, cost를 answer+=
			if(chArr[tmp.point] == 0) {
				answer += tmp.cost;
				chArr[tmp.point] = 1;
				// 연결된 간선 정보 pQ에 넣기
				// !![a 접근 방법]!! graph.get(tmp.point)
				for(Line ob : graph.get(tmp.point)) {
					if(chArr[ob.point] == 0) {
						// pQ에 offer
						pQ.offer(new Line(ob.point, ob.cost));
					}
				}
			}
			
		}
	
		System.out.println(answer);
		
	}

}