[Java] SWEA 1263번 사람 네트워크2

SW Expert Academy

---

풀이

Floyd Warshall 알고리즘을 사용하여 해결했습니다.

---

코드

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

public class Solution {
	public final static int INF = 987654321;
	public static int N;
	public static int[][] adjMatrix;
	public static int[][] dist;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder("");
		StringTokenizer st = null;		
		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; ++tc) {
			st = new StringTokenizer(br.readLine());
			
			N = Integer.parseInt(st.nextToken());
			adjMatrix = new int[N][N];
			
			for (int i = 0; i < N; ++i) {
				for (int j = 0; j < N; ++j) {
					adjMatrix[i][j] = Integer.parseInt(st.nextToken());
					
					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) {
					// 도착지
					for (int j = 0; j < N; ++j) {
						adjMatrix[i][j] = Math.min(adjMatrix[i][j], adjMatrix[i][k] + adjMatrix[k][j]);
					}
				}
			}
			
			int answer = INF;
			for (int i = 0; i < N; ++i) {
				int result = 0;
				for (int j = 0; j < N; ++j) {
					if (adjMatrix[i][j] != INF) {
						result += adjMatrix[i][j];
					}
				}
				
				answer = (answer > result) ? result : answer;
			}
			
			sb.append("#").append(tc).append(" ").append(answer).append("\n");
		}
		
		System.out.println(sb);
	}
}

---

pyo7410/Algorithm