[백준 16398] 행성 연결 (JAVA)

백준(BOJ) 16398 행성 연결

 

난이도
221223 기준 골드 4

사용 알고리즘
최소스패닝트리(MST) - 프림

문제 링크
https://www.acmicpc.net/problem/16398

16398번: 행성 연결

 

 

풀이 과정

 

1. 문제 읽기(중요한 부분 굵은 표시)

 

 홍익 제국의 중심은 행성 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, Cii = 0) 로 주어진다.

 

출력

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

 

 

 

2. 어떤 알고리즘을 사용할 것인가

 

 행성을 노드로 보고 플로우 비용을 간선의 비용으로 보면 최소스패닝트리(MST) 알고리즘으로 풀 수 있어 보입니다. 간선이 N*N개가 나오므로 MST 기법(크루스칼, 프림) 중에 프림을 쓰는게 좀 더 효율적으로 생각되어 프림 알고리즘을 사용하겠습니다.

 

 

3. 풀이 구상

 

 프림 알고리즘을 사용하면 문제는 자연스레 풀릴 것 같고 입력값으로 인접행렬을 주니까 그대로 사용하겠습니다.

 입력값 중에 Cji의 범위가 "1 ≤ Cij≤ 100,000,000" 이기 때문에 관리비용을 int말고 long으로 받아줘야 하는 것만 주의하고 코드를 짜보겠습니다.

 

 

4. 코드 작성

 

1. 정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

// 백준 16398 행성 연결
public class Main {
	
	static int N;
	// 인접 배열
	static int[][] adjMatrix;
	static int[] dist;	
	static boolean[] visited;
	static long resultSum;

    public static void main(String[] args) throws Exception {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    	N = Integer.parseInt(br.readLine());
    	adjMatrix = new int[N][N];
    	dist = new int[N];
    	visited = new boolean[N];
    	
    	Arrays.fill(dist, Integer.MAX_VALUE);
    	
    	for(int r = 0; r < N; r++) {
    		StringTokenizer st = new StringTokenizer(br.readLine());
    		for(int c = 0; c < N; c++) {
    			adjMatrix[r][c] = Integer.parseInt(st.nextToken());
    		}
    	}
    	resultSum = 0;
    	prim();
    	
    	
    	bw.write(resultSum+"");
    	bw.flush();
        bw.close();
        br.close();
    }
    	
    static void prim() {
    	
    	dist[0] = 0;
    	int minidx = -1;
    	int mindist = Integer.MAX_VALUE;
    	for(int i = 1; i < N; i++) {
    		dist[i] = Math.min(dist[i],adjMatrix[0][i]);
    		if(mindist > dist[i]) {
    			mindist = dist[i];
    			minidx = i;
    		}
    	}
    	visited[0]=true;
    	
    	int visitedCnt = 1;
    	
    	while(visitedCnt < N) {
    		
    		visited[minidx]=true;
    		int nextidx = minidx;
    		mindist = Integer.MAX_VALUE;
    		for(int i = 0; i < N; i++) {
    			if(i==nextidx) {
    				continue;
    			}
    			if(visited[i]) {
    				continue;
    			}
    			dist[i] = Math.min(dist[i],adjMatrix[nextidx][i]);
    			if(mindist > dist[i]) {
    				mindist = dist[i];
    				minidx = i;
    			}
    		}
    		visitedCnt++;
    	}
    	
    	for(int i = 0; i < N; i++) {
    		resultSum += dist[i];
    	}
    	
    }
 

}

 

2. 주의할 점

 

 프림 알고리즘을 알고 있으면 문제 자체는 쉽게 풀 수 있습니다. 입력값으로 주어지는 인접행렬을 그대로 사용하면 됩니다.

 시간복잡도의 관점에서 보면 최소간선을 갱신하고 그 다음 가까운 행성을 구하는 부분에서 PriorityQueue를 사용하면 정점의 수가 V 간선의 수가 E라 했을떄 시간복잡도가 O(ElogV)이고 for문을 돌리면 시간 복잡도가 O(V^2)입니다.

 이 문제의 경우 E = 1000000 이고 V^2 = 1000000이므로 PQ를 쓰는 O(ElogV)가 시간 복잡도가 더 크다는 것을 알 수 있습니다.

 물론 이 문제에서 시간초과가 나지는 않겠지만 언뜻 속도가 빨라보이는 PQ로 푸는 방법이 언제나 시간 복잡도에서 유리한 건 아니라는 것만 체크하시면 됩니다.

 

 

풀이 후기

 MST 문제 자체를 오랜만에 풀어서 프림 알고리즘을 떠올리는데 시간이 좀 걸렸습니다. MST 문제는 MST 알고리즘을 알고 있냐 없냐로 문제를 풀 수 있냐 없냐가 갈리기 때문에 꾸준히 복습해야 합니다.