BOJ - 택배 1719번 (JAVA)

❓ 문제 - 백준 택배 1719번 - JAVA 풀이법

 

출처 

(https://www.acmicpc.net/problem/1719)

1719번: 택배

 

 

📝 문제해결법

1. 문제 해석

• 각 집하장 사이를 오갈 때 최단 거리로 오고 갈 수 있어야 한다.
• 따라서 두 집하장 사이를 최단 거리를 오갈 수 있을 경우에 가장 먼저 거쳐야 하는 집하장을 구하여야 한다.

 

2. 변형된 플로이드 워셜을 활용하여 문제를 해결하였습니다.

• 플로이드 워셜의 경우 시간 복잡도는 O(V^3)이기 때문에 문제에서 n이 200 이하이므로 500보다 작기 때문에 플로이드 워셜 알고리즘을 활용하여 구할 수 있습니다. -> 다익스트라도 가능..
• 문제에서 주어진 것은 각 노드 간의 최단 거리가 아닌, 최단 거리르 이동할 때 가장 먼저 거쳐야 하는 집하장을 구해야하는 것이다.
  • 따라서 path 2차원 배열에 a->b로 노드를 이동할 때 가장 먼저 거쳐야 하는 집하장의 번호를 담아서 마지막에 이것을 출력한다.
  • 초반에 a->b 로 이동하면 첫 구간은 b가 되며, a -> k -> b로 이동할 때 첫 구간은 c가 된다.
  • 따라서 path[a][b]에 대해서 첫 구간은 도착지점인 b가 된다.
  • 플로이드 워셜을 구하는 부분에서 [i][j] = [i][k] + [k][j] 인 부분에서 첫 구간은 중간지점의 [i][k]가 된다.

 

3. 느낀점

• 처음에 문제를 딱 보고 플로이드 워셜이나 다익스트라구나 하고 자세히 안보고 코드 작성하다가.. 실수 했다는 것을 깨달았다.
• 다음부터는 풀이법이 바로 떠오른다고 해도 다시 한번 문제를 살피면서 내 문제해설에 오류가 없는지 검토 해야겠다.

 

 

💻 소스코드 

// BOJ - 택배(1724번)
// 플로이드 워셜
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main_1719 {
    public static int n, m;
    public static int[][] distance, path;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        distance = new int[n+1][n+1];
        path = new int[n+1][n+1];


        for(int i=1;i<=n;i++){
            Arrays.fill(distance[i], 10000*1000-1);
            distance[i][i] = 0;
        }

        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());
            path[a][b] = b;
            path[b][a] = a;
            distance[a][b] = Math.min(distance[a][b], c);
            distance[b][a] = Math.min(distance[b][a], c);
        }

        for(int k=1;k<=n;k++){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    if(k == i) continue;
                    if(distance[i][j] > distance[i][k]+distance[k][j]){
                        distance[i][j] = distance[i][k]+distance[k][j];
                        path[i][j] = path[i][k];
                    }
                }
            }
        }

        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i == j) {
                    System.out.print("-" + " ");
                    continue;
                }
                System.out.print(path[i][j] + " ");
            }
            System.out.println();
        }

    }
}