[백준/자바] 16398 행성 연결

16398 행성 연결 사진 클릭시 문제로 이동

---

문제

홍익 제국의 중심은 행성 T이다.

제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다.

두 행성 간에 플로우를 설치하면 제국의 함선과 무역선들은 한 행성에서 다른 행성으로 무시할 수 있을 만큼 짧은 시간만에 이동할 수 있다.

하지만, 치안을 유지하기 위해서 플로우 내에 제국군을 주둔시켜야 한다.

모든 행성 간에 플로우를 설치하고 플로우 내에 제국군을 주둔하면, 제국의 제정이 악화되기 때문에 황제 윤석이는 제국의 모든 행성을 연결하면서 플로우 관리 비용을 최소한으로 하려 한다.

N개의 행성은 정수 1,…, N으로 표시하고, 행성 i와 행성 j사이의 플로우 관리비용은 Cij이며, i = j인 경우 항상 0이다.

제국의 참모인 당신은 제국의 황제 윤석이를 도와 제국 내 모든 행성을 연결하고, 그 유지비용을 최소화하자. 

이때 플로우의 설치비용은 무시하기로 한다.

입력

입력으로 첫 줄에 행성의 수 N (1 ≤ N ≤ 1000)이 주어진다.

두 번째 줄부터 N+1줄까지 각 행성 간의 플로우 관리 비용이 N x N 행렬 (Cij),  

(1 ≤ i, j ≤ N, 1 ≤ Cij ≤ 100,000,000, Cij = Cji)로 주어진다.

출력

모든 행성을 연결했을 때, 최소 플로우의 관리비용을 출력한다.

예제 입력 1

3
0 2 3
2 0 1
3 1 0

예제 출력 1

3

예제 입력 2

5
0 6 8 1 3
6 0 5 7 3
8 5 0 9 4
1 7 9 0 6
3 3 4 6 0

예제 출력 2

11

---

설명

해당 문제는 다음 알고리즘 분류를 가진다.

• 그래프 이론
• 최소 스패닝 트리

최소 스패닝 트리를 해결하는 알고리즘 중 프림을 이용해 문제를 해결했다.

입력이 대칭행렬임을 이용해 i행 j열의 가중치 값을 다음과 같이 입력받는다.

for(int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j = 0; j < n; j++) {
				int w = Integer.parseInt(st.nextToken());
				graph[i].add(new edge(j, w)); // i행 j열의 가중치 w
			}
}

 

가중치를 오름차순으로 정렬하고 이를 이용해 우선순위 큐를 사용한다.

static class edge implements Comparable<edge>{
		int node;
		int weight;
		
		edge(int node, int weight) {
			this.node = node;
			this.weight = weight;
		}

		// 가중치를 오름차순으로 정렬
		@Override
		public int compareTo(edge o) {
			return weight - o.weight;
		}
}

방문했던 정점을 제외하고 새로 방문하는 노드의 개수가 정점의 개수가 될 때까지 prim알고리즘이 동작한다.

static void prim() {
		pq.add(new edge(0,0));
		
		while(!pq.isEmpty()) {
			edge cur = pq.poll();
			
			if(visited[cur.node]) {
				continue;
			}
			visited[cur.node] = true;
			
			result += cur.weight;
			
			for(edge next : graph[cur.node]) {
				if(!visited[next.node]) {
					pq.add(next);
				}
			}
			
			if(++count == n) {
				break;
			}
		}
}

 

코드