[SWEA-1263] 사람 네트워크2

이 문제는 swea D6 레벨 문제이다. 

 

 

이 문제는 플로이드-마샬, Floyd 알고리즘을 가지고 풀었다. 

 

1) 모든 경유지에 대해서

2) 출발지부터 도착지까지 가는데, 경유지를 거쳐서 가는 것과 바로 가는 것 중에 작은 값을 저장해준다.

 

라는 어찌보면 간단한 완전탐색 알고리즘이다. 

근데 만약 이 알고리즘을 배우지 않았다면 좀 많이 헤맸을 것 같다. 

 

import java.util.Scanner;

public class 사람네트워크2 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int tc=1; tc<=T; tc++) {
			int N = sc.nextInt();
			int[][] map = new int[N][N];
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++){
					map[i][j] = sc.nextInt();
					if(i != j && map[i][j] == 0)
						map[i][j] = 100000;
				}
			}

			int cnt = 0;
			int min = Integer.MAX_VALUE;
			
			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 || j==k) //목적지와 경유지가 같거나, 출발지와 목적지가 같으면 갈 필요 없음 
							continue;
						
						map[i][j] = Math.min(map[i][k]+map[k][j], map[i][j]);
					}
				}
			}			
			
			for(int i=0; i<N; i++) {
				cnt = 0;
				for(int j=0; j<N; j++) {
					cnt += map[i][j];
				}
				if(cnt < min)
					min = cnt;
			}
			System.out.println("#"+tc+" "+min);
		}
	}

}