[자바] 백준 11404 - 플로이드

플로이드 와샬 알고리즘에 대한 문제.

모든 정점에서 모든 정점에 대한 최단 거리를 구할 때 사용하는 알고리즘으로, 일종의 DP라고 한다. 

 

3중 for문으로 해결을 하는데

1번째 for문 : 경유지 k

2번째 for문 : 시작점 i

3번째 for문 : 종료점 j

 

이렇게 모든 N에 대해 3중 for문을 돌리기 때문에 정점의 개수가 적은 문제에서만 적용이 가능하다. 

기본적인 아이디어는 경유지의 입장에서 생각을 하는 거다. 

시작점 i가 나한테 오는 최단거리 + 내가 종료점 j로 가는 최단거리가 시작점 i에서 종료점 j로 바로 가는 최단거리 보다 작으면 값을 갱신해준다. 

 

처음 조금 의심이 들었던 부분은 정말 모든 경우에 대해서 최단 거리로 갱신이 가능한지 였다.

예를 들어 2 →4(경유)→1(경유) →5 로 가는 경로가 최단 거리라고 하자.

그리고 (2,4) (4,1) (1,5) 이렇게 연결되어 있기 때문에 4에서 5로 가는 방법도 1을 경유하는 방법 밖에는 없다. 

처음에는 시작지(2)의 입장에서 생각을 했었는데, 그러다 보니까 이미 4(경유)의 for문을 타고 있는데, 4에서 5로 가는 최단 거리인 4 → 1(경유) → 5는 누락되는 것 아닌가? 싶었다. 

하지만 그게 아니었다. 플로이드 와샬은 경유지의 입장에서 생각해야 했다.  4 → 1(경유) → 5 는 1의 for문에서 이미 최단 거리를 찾아서 dist[4][5]에 알맞은 값을 넣어주었고, 이제 4의 입장에서 생각해보면 dist[2][4](직접적으로 이어져있는 최단 거리) + dist[4][5](1을 통해 이어진 최단거리)를 합쳐서 dist[2][5]를 만들어주면 되는 것. 

이 문제는 플로이드 와셜 알고리즘만 알면 풀린다. 가지치기는 필요 없지만, 넣자면 시작지와 경유지, 시작지와 도착지, 경유지와 도착지의 위치가 같은 경우에는 continue를 통해 구문을 스킵했다.

아 그리고 첫 번째 시도 때는 98%쯤에 '틀렸습니다'가 떴었는데, static int MAX = 100001로 초기화한 게 문제였다. 하나의 거리에 최대 10만의 값이 나올 수 있기 때문에, 두 도시가 여태까지 한 번도 연결되지 않았음을 표현하기 위해서는 10만 x N(최대 100)인 1000만 초과로 해주는 게 좋다.

다익스트라와 달리 플로이드 와샬은 간선 값이(즉, 거리) 마이너스여도 사이클만 없으면 최단 거리를 찾을 수 있다는데, 이건 사이클에 대해 조금 더 알았을 때 고민해 봐야 겠다. 

 

/*2020.12.19*/
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	static int MAX = 10000001;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine().trim());
		int M = Integer.parseInt(br.readLine().trim());
		
		int[][] dist = new int[N+1][N+1];
		
		//1. 모든 거리를 MAX 값으로 최대화
		for(int i=1;i<=N;i++) {
			for(int j=1;j<=N;j++) {
				if(i==j) dist[i][j] = 0;
				else dist[i][j] = MAX;
			}
			
		}
		
		//2. 거리 입력 받음
		String[] str;
		int s,e,d;
		for(int i=1;i<=M;i++) {
			str = br.readLine().trim().split(" ");
			s = Integer.parseInt(str[0]);
			e = Integer.parseInt(str[1]);
			d = Integer.parseInt(str[2]);
			
			dist[s][e] = Math.min(dist[s][e], d);
		}
		
		//3. 플로이드 와셜 
		for(int k=1;k<=N;k++) {
			
			for(int i=1;i<=N;i++) {
				if(i==k) continue;
				
				for(int j=1;j<=N;j++) {
					if(i==j || j==k ) continue;
					
					dist[i][j] = Math.min(dist[i][j], dist[i][k]+dist[k][j]);
				}
			}
		}
		
		//4. 출력
		StringBuilder sb = new StringBuilder();
		for(int i=1;i<=N;i++) {
			for(int j=1;j<=N;j++) {
				if(dist[i][j]==MAX) sb.append("0 ");
				else sb.append(dist[i][j]+" ");
			}
			sb.append("\n");
		}
		
		System.out.println(sb.toString().trim());
	}

}