[JAVA]SWEA_1263_사람네트워크2

문제링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18P2B6Iu8CFAZN&categoryId=AV18P2B6Iu8CFAZN&categoryType=CODE&problemTitle=%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

 

 

 

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

public class Solution {

	static final int INF = 9999999;
	static int N;
	static int map[][];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		
		for(int t=0;t<T;t++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			
			map = new int[N][N];
			
			for(int i=0;i<N;++i) {
				for(int j=0;j<N;++j) {
					map[i][j] = Integer.parseInt(st.nextToken());
					if(i!=j && map[i][j]==0) map[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(map[i][j]>map[i][k]+map[k][j]) {
							map[i][j] = map[i][k] + map[k][j];
						}
					}
				}
			}
			
			System.out.println("#"+(t+1)+" "+getResult());
		}
	}
	
	static int getResult() {
		int res = Integer.MAX_VALUE;
		
		for(int i=0;i<N;i++) {
			int sum = 0;
			for(int j=0;j<N;j++) {
				sum += map[i][j];
			}
			res = Math.min(res, sum);
		}
		
		return res;
	}
}

 

플로이드 사용해서 해결했다.

이렇게 조건이 주어져 있어서 모든 노드를 다 탐색한다고 생각하여 플로이드를 사용하였다.