[백준 JAVA] 1504번: 특정한 최단 경로

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

 

처음엔 N 이 800정도여서 플로이드 워셜로 한번 풀어보았다.

 

800^3 = 5억 정도여서 시간초과가 예상되었지만 이정도에 시간 초과가 나나 궁금하기도 하였다.

 

그래프는 인접 배열로 풀이하였다.

 

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

public class Main {
    static int N, E, v1, v2;
    static int[][] graph;
    static final int INF = 1_000_000;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        graph = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            Arrays.fill(graph[i], INF);
            graph[i][i] = 0;
        }

        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 c = Integer.parseInt(st.nextToken());
            graph[a][b] = c;
            graph[b][a] = c;
        }

//        for (int i = 1; i <= N; i++) {
//            for (int j = 1; j <= N; j++) {
//                System.out.print(graph[i][j] + " " );
//            }
//            System.out.println();
//        }

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

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

        int way1 = graph[1][v1] + graph[v1][v2] + graph[v2][N];
        int way2 = graph[1][v2] + graph[v2][v1] + graph[v1][N];
        int min = Math.min(way1, way2);
        if (min > INF) min = -1;

        System.out.println(min);
    }
}

 

시간초과가 나진 않았지만 60퍼 쯤에서 틀렸다.

 

이건 내가 고려하지 못한 부분이 있는거다.

 

이유를 생각해보니 나는 1부터 v1, v2를 지나 N까지 도달하는 경로가 두개라고 생각했다.

 

1 -> v1 -> v2 -> N

1 -> v2 -> v1 -> N

 

근데 이거는 변하지 않을꺼같다.

 

다른 문제 중 아까 디버깅 중 INF 값이 너무 크다고 생각해 줄여놨는데 이게 문제였다.

최대값은 800 * 1000 정도라 생각해서 INF를 100만정도로 잡았는데 1000만으로 하니까 해결되었다.

 

이유를 분석해보았더니 100만이 문제가 아니라 최종적으로는 세 최단거리의 합으로 경로를 구하는데 이거는 300만이 넘을 가능성도 있다.

 

하지만 내 풀이를 보면 마지막에 min이 INF 를 넘으면 도달할 수 없는 경로라 판단해 -1을 반환하도록 되어있다.

따라서 INF는 100만으로 두고 마지막 검증을 3 * INF로 하면 정답이 되는지 확인해보았다.

결과는 실패다 이전에는 60퍼쯤에서 틀렸는데 이렇게 했더니 75퍼 쯤에서 틀렸다.

 

다시 분석해보니 만약 경로 중 하나만 끊겨있는 경우여도 예를들면 1 -> v1 의 값이 100만 이여도 마지막에 300만으로 체크하고 있어서 이러한 값이 맞는 값으로 들어가서 틀린거같다. 그래서 다시 INF 조건을 걸고 이를 통과해야 way로 인정해주는 방식으로 코드를 고쳐보았다.

 

int way1 = INF;
if (graph[1][v1] < INF && graph[v1][v2] < INF && graph[v2][N] < INF) {
    way1 = graph[1][v1] + graph[v1][v2] + graph[v2][N];
}

int way2 = INF;
if (graph[1][v2] < INF && graph[v2][v1] < INF && graph[v1][N] < INF) {
    way2 = graph[1][v2] + graph[v2][v1] + graph[v1][N];
}

int ans = Math.min(way1, way2);
System.out.println(ans >= INF ? -1 : ans);

 

이렇게 해도 통과가 되지 않았다. 이유는 단순히 “최종 경로 3개 더해서”가 아니라,
플로이드 과정에서 중간 거리 자체가 100만을 넘어갈 수 있기 때문이었다.

 

하지만 나중에 이렇게까지 문제를 풀 필요는 없고 그냥 INF 값을 고민 너무 하지말고 충분히 큰값으로 한다면 해결될일 같다.

 

나는 이전에 INF 값을 너무 크게 설정했다가 플로이드 워셜 연산 중 오버플로우가 생겨 음수값이 발생했다.

그래서 틀린 경험이 있어서 이번에는 INF 를 최소로 두었는데 이런 경우에도 문제가 생기니 적절한 값으로 설정해 두는것이 정답이다.

 

아니라면 플로이드 워셜 과정 중 INF 값이 나오는 경우 최단 거리를 갱신하지 않는 방법도 있을꺼같다.

 

지금은 5억 정도 수준이라 빠듯하게 통과하지만 이를 다익스트라로 풀면 좀 더 여유있게 통과할 수 있을꺼같아서 최단거리를 판단해주는 부분만 다익스트라로 바꿔보았다.

 

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

public class Main {
    static int N, E, v1, v2;
    static int[] dist;
    static List<int[]>[] graph;
    static final int INF = 10_000_000;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        graph = new List[N + 1];
        for (int i = 1; i <= N; i++) graph[i] = new ArrayList<>();
        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 c = Integer.parseInt(st.nextToken());
            graph[a].add(new int[] {b, c});
            graph[b].add(new int[] {a, c});
        }

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

        int way1 = dijkstra(1, v1) + dijkstra(v1, v2) + dijkstra(v2, N);
        int way2 = dijkstra(1, v2) + dijkstra(v2, v1) + dijkstra(v1, N);
        int min = Math.min(way1, way2);

        System.out.println(min >= INF ? -1 : min);
    }

    private static int dijkstra(int u, int v) {
        dist = new int[N + 1];
        Arrays.fill(dist, INF);
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1[1], o2[1]));
        pq.offer(new int[] {u, 0});
        dist[u] = 0;
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int now = cur[0];
            int nowDist = cur[1];
            if (nowDist > dist[now]) continue;
            for (int[] next : graph[now]) {
                int cost = nowDist + next[1];
                if (dist[next[0]] > cost) {
                    dist[next[0]] = cost;
                    pq.offer(new int[] {next[0], cost});
                }
            }
        }
        return dist[v];
    }
}

 

다익스트라로 풀면 시간이 O(E log V) 수준이라 플로이드워셜 O(N^3)보다 훨씬 작은 수준으로 문제를 풀 수 있다.

 

시간은 약 1/3 수준이었다.

 

배운점

1. 플로이드 워셜을 사용할때는 INF를 충분히 큰값으로 설정하되 오버플로우가 나지 않는선에서 사용하자

2. 플로이드 워셜이 구현은 간단하지만 이렇게 특정 최단거리만 구해도 되는 경우는 다익스트라를 사용하는게 시간 복잡도를 줄일 수 있다.