[백준] 1719번. 택배(JAVA)

문제

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

---

풀이(32분)

import java.io.*;
import java.util.*;

public class Main {

    static int n, m;
    static int[][] floyd;
    static int[][] idx;
    static boolean[][] edges;

    static final int MAX = 1_000_000_000;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken()); // 정점의 개수
        m = Integer.parseInt(st.nextToken()); // 간선의 개수
        floyd = new int[n+1][n+1];
        idx = new int[n+1][n+1];
        edges = new boolean[n+1][n+1];

        for(int i = 0; i < n+1; i++){
            Arrays.fill(floyd[i], MAX); // 경로 최초값 수정
        }
        for(int i = 0; i < n+1; i++){
            floyd[i][i] = 0; // 자기 자신에 대한 경로는 0으로 초기화
        }

        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int time = Integer.parseInt(st.nextToken());
            floyd[start][end] = time; // 최초 값
            floyd[end][start] = time; // 최초 값
            idx[start][end] = end; // 최초 값
            idx[end][start] = start; // 최초 값
            edges[start][end] = true;
            edges[end][start] = true;
        }

        floyd();
        StringBuilder sb = new StringBuilder();
        for(int i = 1; i < n+1; i++){
            for(int j = 1; j < n+1; j++){
                if(idx[i][j] == 0){
                    sb.append("-").append(" ");
                    continue;
                }
                sb.append(idx[i][j]).append(" ");
            }
            sb.append("\n");
        }

        System.out.println(sb);
    }

    static void floyd(){
        for(int k = 1; k < n+1; k++){
            for(int i = 1; i < n+1; i++){
                for(int j = 1; j < n+1; j++){
                    int temp = floyd[i][k] + floyd[k][j];
                    if(floyd[i][j] > temp){
                        floyd[i][j] = temp;
                        if(idx[i][k] == 0){
                            idx[i][j] = k;
                            continue;
                        }
                        idx[i][j] = idx[i][k];
                    }
                }
            }
        }
    }
}

---

문제 풀이 전략

 

모든 경로 상의 최단 거리를 알아야 하는 문제이기 때문에 먼저 플로이드-와샬 알고리즘을 떠올렸고, 적용했다.

[도구정리] 플로이드-와샬(Floyd-Warshall) 알고리즘

 

알고리즘을 적용하는 과정에서 만약 경로가 업데이트된다면 최초로 거쳐간 점도 수정해줘야 한다.

 

1. 경로가 업데이트된 적이 없다면

-> k를 최초 노드로 정한다.

 

2. 이미 경로가 업데이트 된 적이 있다면

-> i->k까지 이동할 때의 최초 점을 최초 노드로 정한다.

 

두 가지 과정만 추가해 주면 되는 문제였다.