[BOJ-11404] 플로이드 -Java

https://www.acmicpc.net/problem/11404

11404번: 플로이드

package 그래프;

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

public class boj_11404_플로이드 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
		
		int n=Integer.parseInt(br.readLine());
		int m=Integer.parseInt(br.readLine());
		StringTokenizer st = null;
		int map[][]= new int [n+1][n+1];
		
		for(int i=0; i<m; i++) {
			st=new StringTokenizer(br.readLine());
			int a=Integer.parseInt(st.nextToken());
			int b=Integer.parseInt(st.nextToken());
			int c=Integer.parseInt(st.nextToken());
			if(map[a][b]==0) map[a][b]=c;
			else map[a][b]=Math.min(map[a][b], c);
		}
		
		for(int k=1; k<=n; k++) {
			for(int i=1; i<=n; i++) {
				for(int j=1; j<=n; j++) {
					if(map[i][k]==0 || map[k][j]==0 || i==j) continue;
					if(map[i][j]==0) map[i][j]=map[i][k]+map[k][j];
					else if(map[i][j]>map[i][k]+map[k][j]) map[i][j]=map[i][k]+map[k][j];
					
				}
			}
		}
		
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				System.out.print(map[i][j]+" ");
			}
			System.out.println();
		}
		
	}

}

 

소요시간 : 25분

 

모든 도시의 쌍(A,B) 에 대해서 도시 A에서 B로 가는최솟값을 구하는 문제다.

물론 문제 제목도 플로이드이지만 문제 내용과 (2<=n<=100) 이라는 내용을 살펴보면 플로이드 와샬 알고리즘이 가장먼저 떠오른다!

 

우선 3중포문 (i : 출발지, j:도착지, k:경유지)를 돌리면서

i와 j가 같거나, 경유해서 갈 수 없는 곳(map[i][k], map[k][j] 중 하나라도 0 )이라면 skip한다.

 

만약 map[i][j]가 0이라면 경유해서 갈 수 있는 곳의 값을 더해서 넣어준다.

만약 map[i][j]가 0이 아니라면 현재 값보다 경유해서 가는 값이 더 최솟값이라면 바꿔준다!

 

 

처음에 입력으로 들어오는 부분에서 출발지와 도착지는 겹치지 않는다 라는말이 

1 2 10

1 2 5

이런식으로 안들어온다고 이해했는데 문제를 풀다가 이상해서 다시보니 

1 1 10 이런경우가 없다는 내용이었다..

이거때문에 한 10분 잡아먹은듯...

 

문제를 잘 읽자