[SWEA] 1263. 사람 네트워크 2 (Java)

 

문제

SW Expert Academy

 

알고리즘

그래프, 플로이드 워셜(Floyd Warshall)

 

 

풀이

사용자 i의 다른 모든 사용자까지의 최단거리의 합을 CC(i) 라고 할 때, 모든 사용자의 CC 값 중 최솟값을 출력하는 문제이다.

 

따라서 플로이드 워셜 알고리즘을 이용해 모든 사용자로부터 다른 모든 사용자까지의 최단거리를 구하고

각 사용자마다 다른 모든 사용자까지 가는 최단 거리의 합(CC(i))을 구하고 최솟값을 갱신한다.

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		for(int t=1; t<=T; t++) {
			st = new StringTokenizer(br.readLine(), " ");
			int N = Integer.parseInt(st.nextToken());
			int[][] dist = new int[N][N];
			
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					dist[i][j] = Integer.parseInt(st.nextToken());
					if(i!=j && dist[i][j] == 0)
						dist[i][j] = 87_654_321;
				}
			}
			
			for(int k=0; k<N; k++) {
				for(int i=0; i<N; i++) {
					for(int j=0; j<N; j++) {
						dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
					}
				}
			}
			
			int min = 87_654_321;
			for(int i=0; i<N; i++) {
				int sum = 0;
				for(int j=0; j<N; j++) {
					sum += dist[i][j];
				}
				min = Math.min(min, sum);
			}
			sb.append("#").append(t).append(" ").append(min).append("\n");
			
		}
		
		System.out.println(sb);
	}
}