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

[문제]

1504번: 특정한 최단 경로

 

📒 문제

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

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

 

📒 문제 풀이

배열을 생성해 무방향 그래프를 구현한 뒤, 플로이드 와샬을 통해 접근 가능한 인접 행렬의 개수를 구한다. 이 배열을 통해 반드시 거쳐야 하는 두 개의 정점을 1 -> v1 -> v2 -> N 혹은 1 -> v2 -> v1 -> N의 경로의 최단거리를 찾아 출력한다.

 

📒 소스코드

package BOJ.Graph;

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

public class boj1504_특정한최단경로 {
    public static void main(String[] args) throws Exception {
        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[][] graph = new long[N + 1][N + 1];
        long INF = 200000000;

        for (int i = 0; i < N + 1; i++) {
            for (int j = 0; j < N + 1; j++) {
                if (i == j) {
                    graph[i][j] = 0;
                }
                graph[i][j] = INF;
            }
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            long value = Integer.parseInt(st.nextToken());

            graph[v1][v2] = value;
            graph[v2][v1] = value;
        }

        st = new StringTokenizer(br.readLine(), " ");
        int via1 = Integer.parseInt(st.nextToken());
        int via2 = Integer.parseInt(st.nextToken());

        for (int via = 1; via < N + 1; via++) {
            for (int from = 1; from < N + 1; from++) {
                for (int to = 1; to < N + 1; to++) {
                    if (graph[from][to] > graph[from][via] + graph[via][to]) {
                        graph[from][to] = graph[from][via] + graph[via][to];
                    }
                }
            }
        }

        long result1 = 0;
        long result2 = 0;

        result1 = graph[1][via1] + graph[via1][via2] + graph[via2][N];
        result2 = graph[1][via2] + graph[via2][via1] + graph[via1][N];

        if (via1 == 1 || via2 == 1) {
            if (via1 == N || via2 == N) {
                if (graph[1][N] >= INF) {
                    System.out.println("-1");
                } else {
                    System.out.println(graph[1][N]);

                }
            }
        } else if (result1 >= INF || result2 >= INF) {
            System.out.println("-1");
        } else {
            long result = Math.min(result1, result2);
            System.out.println(result);

        }

    }
}

 

📒 리뷰

 

---

이 문제는 사실 플로이드 와샬이 아닌 다익스트라로 풀어야 효율성이 더 좋아지는 문제인 것 같다.

출발해야 하는 지점을 모를 때는 플로이드 와샬로 경유지를 모조리 찾아 확인하는 게 편리하지만

출발지와 도착지를 아는 시점에서는 다익스트라가 더 시간적으로, 메모리적으로도 효율성이 높아질 것 같다.

다음에 다시 다익스트라로 풀어봐야징..🙄🙄🙄