알고리즘/SwExpert recipe

[SWEA] 사람 네트워크 D6

컵라면만두세트 2021. 3. 25. 23:15

플루이드 워샬 알고리즘 참고

import java.util.Scanner;

public class 사람네트워크 {
	static int T , N;
	static final int INF = 999999;
	static int adjMatrix[][];
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int tc = 1; tc<=T; tc++) {
			N = sc.nextInt();
			adjMatrix = new int[N][N];
			
			for(int i =0; i<N; ++i) {
				for(int j =0; j<N; ++j ) {
					adjMatrix[i][j] = sc.nextInt();
					if(i !=j && adjMatrix[i][j] == 0) {
						adjMatrix[i][j] = INF;
					}
				}
			}
			
			for(int k =0; k<N; ++k) {
				for(int i =0; i<N; ++i) {
					if(i==k) continue; // 이건 자기 자신을 경우에서 가니까 빼준다
					for(int j =0; j<N; ++j) {
						if(i==j || k==j) continue;
						if(adjMatrix[i][j] > adjMatrix[i][k] + adjMatrix[k][j]) {
							adjMatrix[i][j] = adjMatrix[i][k] + adjMatrix[k][j];
						}
					}
				}
			}
			int min = Integer.MAX_VALUE;
			for(int i =0; i<N; ++i){
				int sum = 0;
				for(int j= 0; j<N; ++j) {
					sum+= adjMatrix[i][j];
					
				}
				if(sum<min) {
					min = sum;
				}
			}
			System.out.println("#" + tc + " " + min);
			
		}
	}

}