Q. 5719 자바 : 거의 최단 경로

Q. 5719자바 : 거의 최단 경로

 

문제 : boj.kr/5719

P5 난이도의 문제이다.

 

문제를 간단히 설명하자면 거의 최단 경로를 찾는 문제이고

거의 최단 경로란 최단 경로에 포함되지 않는 도로로만 이루어진 경로 중 가장 짧은 것을 말한다. 

 

거의 최단 경로를 찾기 위해서는 먼저 최단 경로를 찾아야 한다.

그리고 경로 추적을 이용해 어떤 간선을 통해 최단 경로에 도달했는지 파악하고 해당 간선들을 끊어준 뒤

다시 최단 경로를 계산하면 거의 최단 경로를 구할 수 있다.

---

아래와 같은 방식으로 풀었다.

 

0. 입력값에 대해 정방향 그래프와 더불어 역방향 그래프를 저장한다.

1. 시작점으로 부터 정방향 그래프와 다익스트라 알고리즘을 활용해 최단 경로를 계산한다.

2. 도착점에서 역방향 그래프와 BFS를 활용해 어떤 간선이 최단 경로에 활용된 간선인지 찾는다.

1번 연산의 결과값 dist[] 배열이 있다고 가정하자.

이는 x부터 A, B, C, D, E, y까지의 최단 경로가 저장된 배열이다.

그리고 x부터 y까지 가는 최단 경로를 관찰해보자.

x부터 y로 가는 최단 경로는 x부터 B로 가는 최단 경로 또는 x부터 D로 가는 최단 경로를 통하는 것을 알 수 있다.

즉 x부터 y로 가는 최단 경로는 x에서 다른 정점으로의 최단 경로가 포함되는것을 알 수 있다.

 

만약 x -> D -> y 경로의 최단 경로를 사용한다면

dist[y]와 dist[D]와 간선 D->y의 비용을 활용한다면 최단 경로에 어떤 경로가 포함되었는지 알 수 있다. 

그렇기 때문에 다익스트라 알고리즘의 결과값과 역방향 BFS를 활용하는 것 이다.

 

추가적으로 하나 신경써야 하는 내용으로

BFS에서 방문한 정점은 재방문해서는 안되지만 그 정점을 통한 최단경로는 여러가지가 있을 수 있다.
예를들어 s -> e로 가는 최단경로가
(s -> a -> b -> e), (s -> a -> c -> e) 로 2가지가 있을 수 있는데
이 때 최단경로를 구하기 위해 역방향 BFS 알고리즘을 활용한다면
a 정점을 두 번 넣어주게 되므로 이를 visit 체크를 통해 한 번만 넣도록 한다.
즉 최단 경로중 하나이므로 해당 간선은 지워주되, 만약 visit 체크가 되어있다면 그 정점은 que에 넣어주지 않는다.

그리고 최단 경로에 포함된 간선의 경우 MAX_VALUE로 변경한다.

 

이후 다시 한번 다익스트라를 돌리면 두 번째 최단경로를 구할 수 있다.

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


public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    static final int INF = Integer.MAX_VALUE;

    static class Info{
        int idx;
        long dist;

        Info(int _idx, long _dist) {
            idx = _idx; dist = _dist;
        }
    }

    static int[][] graph, revGraph;
    static int n, m, s, d;
    static long[] minDist;

    static boolean[][] visitEdge;
    static boolean[] visitVertex;

    static void input() throws Exception{

        st = new StringTokenizer(br.readLine());

        s = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());

        graph = new int[n][n];
        revGraph = new int[n][n];

        visitEdge = new boolean[n][n];
        visitVertex = new boolean[n];

        int u, v, w;
        for (int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
            w = Integer.parseInt(st.nextToken());
            graph[u][v] = w;
            revGraph[v][u] = w;
        }
    }

    static void dijkstra(int start) {
        minDist = new long[n];
        for (int i = 0; i < n; i++) minDist[i] = INF;
        minDist[start] = 0;

        PriorityQueue<Info> pq = new PriorityQueue<>((o1, o2) -> Long.compare(o1.dist, o2.dist));
        pq.add(new Info(start, 0));

        while (!pq.isEmpty()) {

            Info cur = pq.poll();

            if (cur.dist != minDist[cur.idx]) continue;
            for (int next = 0; next < n; next++) {
                if(graph[cur.idx][next] == 0) continue;
                if (minDist[next] > cur.dist + (long)graph[cur.idx][next]) {
                    minDist[next] = cur.dist + (long)graph[cur.idx][next];
                    pq.add(new Info(next, minDist[next]));
                }
            }
        }
    }

    static void bfs(int end) {
        boolean[] visit = new boolean[n];
        visit[end] = true;

        Deque<Integer> que = new ArrayDeque<>();
        que.add(end);

        while (!que.isEmpty()) {

            int cur = que.poll();

            for (int next = 0; next < n; next++) {
                if (revGraph[cur][next] == 0) continue;
                if (minDist[next] == minDist[cur] - revGraph[cur][next]) {
                    graph[next][cur] = INF;

                    if (visit[next]) continue;
                    visit[next] = true;
                    que.add(next);
                }

            }
        }
    }


    static void pro() {
        dijkstra(s);
        bfs(d);
        dijkstra(s);

        if (minDist[d] >= INF) minDist[d] = -1;
        sb.append(minDist[d]);
        sb.append('\n');
    }

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

        while (true) {
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            if (n == 0 && m == 0) break;

            input();
            pro();
        }
        System.out.println(sb);
    }
}