[SW Academy] 1263 사람 네트워크2 - JAVA

1. 문제유형 : 플로이드-워샬

2. 시간복잡도 : O(N^3)

 

수업시간에 배운 플로이드-워샬의 적용 문제였다. 다익스트라 알고리즘 대신 사용할 수 있는 알고리즘이며, 가중치가 음수인 경우에도 사용할 수 있다.

코드는 쉬우나 알고리즘 이론을 잊지 않도록 자주 복습해두자.

 

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

public class Solution {

	static final int INF = 9999;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(in.readLine());
		for (int tc = 1; tc <= T; tc++) {
			String s = in.readLine();
			String[] spt = s.split(" ");
			int N = Integer.parseInt(spt[0]);
			int len = (int) Math.sqrt(spt.length-1);
			int[][] matrix = new int[len][len];
		
			for (int row = 0; row < len; row++) {
				for (int col = 0; col < len; col++) {
					matrix[row][col] = Integer.parseInt(spt[len*row+(col+1)]);
					if(row != col && matrix[row][col] == 0) matrix[row][col] = INF;
				}
			}
			
			for (int cross = 0; cross < len; cross++) {
				for (int from = 0; from < len; from++) {
					if(cross == from) continue;
					for (int to = 0; to < len; to++) {
						if(from == to || cross == to) continue;	// 출발지 도착지가 같을 때
						matrix[from][to] = Math.min(matrix[from][to], matrix[from][cross] + matrix[cross][to]);
					}
				}
			}
			
			int min = Integer.MAX_VALUE;
			for (int i = 0; i < matrix.length; i++) {
				int cc = 0;
				for (int j = 0; j < matrix.length; j++) {
					if(i == j) continue;
					cc += matrix[i][j];
				}
				min = Math.min(min, cc);
			}
			System.out.println("#" + tc + " " + min);
		}
	}

}