[백준] 23258. 밤편지 (Java)

 

문제

23258번: 밤편지

 

알고리즘

다이나믹 프로그래밍(DP), 플로이드-워셜 알고리즘(Floyd Warshall)

 

풀이

Q가 최대 50만으로 V² 보다 훨씬 크기 때문에 다익스트라 알고리즘을 이용하면 시간 초과가 날 것이다.

따라서 V³의 플로이드 워셜 알고리즘으로 모든 경우의 값을 저장하고 이를 출력한다.

 

만약 C가 3인 반딧불이는 어느 마을까지 이동할 수 있을까

2³ = 8 방울을 마실 수 있으므로 3번 마을부터는 이동할 수 없을 것이다. 

1번 마을에서 2¹ = 2 방울,

2번 마을에서 2² = 4 방울을 마시기 때문에

3번보다 번호가 작은 모든 마을을 모두 방문해도 8방울 이상 마시는 경우는 없다.

 

즉, 2^C > 2¹+2²+..+2^C-1  이므로

C가 i라는 말은 해당 반딧불이가 i번 마을보다 작은 모든 마을을 방문할 수 있다는 뜻이다.

 

플로이드 워셜 알고리즘은 모든 지점에 대해,

해당 지점을 중간 지점으로 삼고 그 지점을 경유했을 때 더 시간이 낮다면 갱신하는 알고리즘이다.

따라서 모든 중간 지점 k값에 대한 값을 저장해 C가 i 라면 i 번 마을 이전까지만 방문했을 때의 값을 구할 수 있다.

 

이를 위해서 3차원 배열 dist[i][j][k] 가 필요하고,

이는 i번 마을에서 j번 마을까지 가는데 k번 마을까지만 방문했을 때 걸린 최소 시간을 의미한다.

 

점화식은 다음과 같다.

dist[i][j][k] = Math.min(dist[i][j][k-1], dist[i][k][k-1] + dist[k][j][k-1])

 

예를 들어 dist[1][4][3]

즉, 3번 마을까지 방문 가능한 경우 1번부터 4번 마을까지 가는데 걸리는 최소 시간은

2번 마을까지 방문 가능한 경우 1번부터 4번 마을까지 가는데 걸리는 최소 시간 dist[1][4][2]에서 

2번 마을까지 방문 가능한 경우 1번 마을에서 3번 마을을 거쳐 4번 마을까지 가는 시간 dist[1][3][2] + dist[3][4][2] 과 비교한 값 중 작은 값이다. 

 

플로이드 워셜 알고리즘의 원리를 제대로 알고 있어야하기 때문에 공부하기 좋은 문제인 것 같다.

 

 

코드

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

public class Main {
	static final int MAX = 87_654_321;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int Q = Integer.parseInt(st.nextToken());
		
		int[][][] dist = new int[N+1][N+1][N+1];
		
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine() ," ");
			for(int j=1; j<=N; j++) {
				int num = Integer.parseInt(st.nextToken());
				
				if(i==j) continue;
				dist[i][j][0] = num == 0 ? MAX: num;
			}
		}
		
		for(int k=1; k<=N; k++) {
			for (int i=1; i<=N; i++) {
				for(int j=1; j<=N; j++) {
					
					dist[i][j][k] = Math.min(dist[i][j][k-1], dist[i][k][k-1] + dist[k][j][k-1]);
				}
			}
		}
		
		for(int i=0; i<Q; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int C = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			
			if(dist[s][e][C-1] == MAX)
				sb.append("-1\n");
			else 
				sb.append(dist[s][e][C-1]).append("\n");
		}
		
		System.out.println(sb);
	}
}