백준 23258번: 밤편지 (Java)

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

23258번: 밤편지

 

---

 

풀이

2^C > (1 + 2 + ... + 2^(C-1)) 이므로, 2^C 미만만큼 이슬을 먹을 수 있는 반딧물은 1~C-1 칸을 거쳐서 갈 수 있다. 따라서, 3차원 int 배열 d[시작점][끝점][플로이드 단계(0이상 N이하)]를 '해당 플로이드 단계에서 시작점에서 끝점까지 가는 최소 거리'로 정의하여, 플로이드를 하면서 d를 채운다.

 

배운 점

초기화할 때 조심하기: s==e일 때 0을 출력해야하는데, 변수를 잘못 초기화했다.

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
    
    static final int INF = 1_000_000_007;
 
    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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 temp = Integer.parseInt(st.nextToken());
                if (i == j) continue;
                dist[i][j][0] = ((temp == 0)? INF: temp);
            }
        }
        
        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] == INF) sb.append(-1+"\n");
            else sb.append(dist[s][e][C-1]+"\n");
        }
        System.out.println(sb.toString());
    }
}
 

 

---

 

 

여담

https://www.youtube.com/watch?v=BzYnNdJhZQw 

훈련소 밤에 이 노래 틀어줬던 기억이 난다. 눈물날 뻔ㅠ