🔍 문제

📌 입력

📌 출력

🤔 풀이 까지의 생각

문제에서 얻을 수 있는 힌트는 모두 주워 담아보자.

1. "정점간의 간선은 두 집하장간에 화물 이동이 가능함" 이라는 뜻은 간선간의 방향성이 없이 양방향으로 이동 및 접근이 가능하다는 뜻이다.

2. "최단 경로" 해당 문제는 주어진 그림 및 1의 과정에서 그래프 문제 라는 것을 알 수 있다.
   그래프 문제를 최단 경로로 풀어내는 알고리즘은 벨먼-포드 , 다익스트라, 플로이드 워셜 이다.
   (본인은 순수한 BFS를 통한 문제 해결방식은 간선간의 가중치가 존재하지 않을 때 주로 사용하므로 제외 하도록 하겠다.)

3. 주어진 N 즉, 정점의 개수는 최대 200이다. 플로이드 워셜의 시간복잡도는 0(n^3) 이기 때문에 200^3을 해도 시간 내에 통과할 것 같았다.

4. 단순히 최단 시간을 출력하는 것이 아닌 목적지에 도착하기 까지 거치는 첫번째 정점을 찾는 것 이다.

주어진 4가지의 핵심 단서를 통해서 플로이드 워셜을 사용, 최단 경로로 가중치가 갱신될 때 마다 첫번째 거쳐가는 정점 노드 값을 갱신 해주기로 했다.

💻 제출

📝 제출 코드

import java.io.*;
import java.util.Arrays;
import java.util.Stack;
import java.util.StringTokenizer;


public class Main {
    static int N, M;
    static final int INF = 987654321; //충분히 큰 값
    static int[][] distance;
    static int[][] firstVisited;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        distance = new int[N + 1][N + 1];
        firstVisited = new int[N + 1][N + 1]; //첫 방문 배열

		//초기값 세팅 2 -> 1 정점의 첫 방문 정점은 1 이다.
        // i -> j = j
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                firstVisited[i][j] = j; 
            }
        }
		
        //충분히 큰값 INF 로 초기화
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (i != j) {
                    distance[i][j] = INF;
                }
            }
        }

        for (int i = 0; i < M; i++) {
            StringTokenizer stD = new StringTokenizer(br.readLine(), " ");
            int s = Integer.parseInt(stD.nextToken()); //시작점
            int e = Integer.parseInt(stD.nextToken()); //목적지
            int v = Integer.parseInt(stD.nextToken()); //가중치 , 거리

            if (distance[s][e] > v) { //양방향 연결
                distance[s][e] = v;
                distance[e][s] = v;
            }
        }

        floyd(); //floyd warshall

        bw.write(print() + " ");

        bw.flush();
        bw.close();
        br.close();
    }

    static void floyd() {
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (distance[i][j] > distance[i][k] + distance[k][j]) {
                        //가중치 갱신
                        distance[i][j] = distance[i][k] + distance[k][j];
                        
                        //거리 갱신 시에 첫번째 방문지 갱신
                        firstVisited[i][j] = firstVisited[i][k];
                    }
                }
            }
        }
    }

    static String print() {
        StringBuilder sb = new StringBuilder();

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (i == j) {
                    sb.append("- ");
                } else {
                    sb.append(firstVisited[i][j] + " ");
                }
            }
            sb.append("\n");
        }

        return sb.toString();
    }

}