[백준/JAVA] BOJ 1504 - 특정한 최단 경로

너무 오랜만에 하는 알고리즘... 열심히 놀았으니 다시 꾸준히 해 보자

👀 문제

1504번: 특정한 최단 경로 ✨ 골드 4

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

예제 입력

4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
2 3

예제 출력

7

🔑 키포인트

그래프 이론 플로이드 워셜

✍️ 코드

📍 사실 플로이드 워셜보다는 다익스트라로 푸는 게 더 효율적인 문제
💡 플로이드 워셜로 노선 별 최단 거리를 구해 주고, 1 -> v1 -> v2 -> N과 1 -> v2 -> v1 -> N 중에 더 짧은 거리를 출력해 주면 된다

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

public class BOJ1504_특정한최단경로 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());
        long[][] dist = new long[n + 1][n + 1];
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                if (i != j) {
                    dist[i][j] = Integer.MAX_VALUE;
                }
            }
        }

        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            dist[a][b] = d;
            dist[b][a] = d;
        }

        st = new StringTokenizer(br.readLine());
        int v1 = Integer.parseInt(st.nextToken());
        int v2 = Integer.parseInt(st.nextToken());

        for (int k = 1; k < n + 1; k++) {
            for (int i = 1; i < n + 1; i++) {
                if (i == k) {
                    continue;
                }
                for (int j = 1; j < n + 1; j++) {
                    if (i == j || j == k) {
                        continue;
                    }
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }

        long route1 = dist[1][v1] + dist[v1][v2] + dist[v2][n];
        long route2 = dist[1][v2] + dist[v2][v1] + dist[v1][n];
        long answer = Math.min(route1, route2);
        if (answer >= Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(answer);
        }
    }
}