백준 5719번: 거의 최단 경로 Java Solution

1. Problem Definition & Analysis

그래프에서 최단 경로를 구성하는 간선을 제외한 간선들을 사용했을 때의 최단 경로의 길이를 구하는 문제이다. 음의 사이클을 형성하지 않기 때문에 다익스트라 알고리즘으로 최단 경로를 구할 수 있고, 역추적 기법을 활용해 최단 경로를 구성하는 모든 간선을 파악할 수 있다.

이 문제를 해결하는 과정은 다음과 같다.

1. 다익스트라 알고리즘으로 최단 경로를 찾는다.
2. 최단 경로를 구성하는 간선을 모두 제거한다.
3. 다익스트라 알고리즘으로 다시 최단 경로를 찾는다.

핵심은 2번 과정이다. 역추적 기법을 활용해 최단 경로를 구성하는 간선을 모두 제거할 것인데, 역추적을 위해 다음과 같은 과정을 다익스트라 알고리즘의 수행 과정 내에 추가한다.

1. 최단 경로가 갱신될 때 간선에 대한 정보(진출 노드)를 초기화한 후 새로이 저장한다.
2. 같은 최단 경로를 가질 때 간선에 대한 정보를 추가한다.

위 과정은 이어서 코드로 보면 더 이해하기 편할 것이다. 이렇게 함으로써 여러 개의 최단 경로가 동일한 정점을 포함할 때에도 해당 간선들의 정보를 모두 유지할 수 있다. 그 다음에는 도착지($D$)로부터 시작하여 출발지($S$)까지 진입 노드 $\rightarrow$ 진출 노드 방향으로 거슬러 올라가며 간선을 제거해 주면 된다. 이 과정을 DFS 로직으로 수행하는 경우가 많던데, BFS로도 수행 가능하다고 생각하여 BFS로 구현했다.

2. Solution

package P5719;

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

class Main {

    static class Pair implements Comparable<Pair> {
        int first, second;

        public Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }

        public int compareTo(Pair other) {
            if (first == other.first)
                return second - other.second;
            return first - other.first;
        }
    }

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

    static final int INF = 100_000_000;

    static int N, M, S, D, U, V, P;
    static int[][] graph;
    static List<List<Integer>> parent;

    public static void main(String[] args) throws IOException {
        int ret;
        while ((ret = solve()) != -INF)
            sb.append(ret).append('\n');
        System.out.println(sb);
    }

    public static int solve() throws IOException {
        if (!initialize())
            return -INF;

        dijkstra(true);
        int ret = dijkstra(false);
        return ret == INF ? -1 : ret;
    }

    public static boolean initialize() throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        if (N == 0 && M == 0)
            return false;
        graph = new int[N][N];
        for (int[] row : graph)
            Arrays.fill(row, INF);

        st = new StringTokenizer(br.readLine());
        S = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());

        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            U = Integer.parseInt(st.nextToken());
            V = Integer.parseInt(st.nextToken());
            P = Integer.parseInt(st.nextToken());
            graph[U][V] = P;
        }

        return true;
    }

    public static int dijkstra(boolean remove) {
        int[] distance = new int[N];
        Arrays.fill(distance, INF);
        boolean[] visited = new boolean[N];
        PriorityQueue<Pair> pq = new PriorityQueue<>();
        parent = new ArrayList<>();
        for (int i = 0; i < N; i++)
            parent.add(new ArrayList<>());

        distance[S] = 0;
        pq.offer(new Pair(0, S));
        while (!pq.isEmpty()) {
            Pair p = pq.poll();
            int curr = p.second;
            if (visited[curr])
                continue;
            visited[curr] = true;

            for (int next = 0; next < N; next++) {
                if (graph[curr][next] == INF)
                    continue;
                if (distance[curr] + graph[curr][next] < distance[next]) {
                    distance[next] = distance[curr] + graph[curr][next];
                    pq.offer(new Pair(distance[next], next));
                    parent.get(next).clear();
                    parent.get(next).add(curr);
                } else if (distance[curr] + graph[curr][next] == distance[next]) {
                    parent.get(next).add(curr);
                }
            }
        }

        if (remove)
            removePathEdges();

        return distance[D];
    }

    public static void removePathEdges() {
        boolean[] visited = new boolean[N];
        Queue<Integer> queue = new LinkedList<>();

        visited[D] = true;
        queue.offer(D);
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            for (int prev : parent.get(curr)) {
                graph[prev][curr] = INF;
                if (!visited[prev]) {
                    visited[prev] = true;
                    queue.offer(prev);
                }
            }
        }
    }
}

핵심은 다익스트라 메서드 내의 다음 코드 블럭이다.

            for (int next = 0; next < N; next++) {
                if (graph[curr][next] == INF)
                    continue;
                if (distance[curr] + graph[curr][next] < distance[next]) {
                    distance[next] = distance[curr] + graph[curr][next];
                    pq.offer(new Pair(distance[next], next));
                    parent.get(next).clear();
                    parent.get(next).add(curr);
                } else if (distance[curr] + graph[curr][next] == distance[next]) {
                    parent.get(next).add(curr);
                }
            }

최단 경로가 갱신될 때 기존의 진입 노드(next)의 진출 노드들에 대한 정보(parent)를 초기화하고 새로운 진출 노드(next)를 저장한다. 만약 최단 경로가 동일하다면 정보를 초기화하지 않고 진출 노드(next)만 추가한다.

그리고 메서드 매개변수로 플래그를 받아 간선을 제거할지 여부를 결정하도록 하였다. 메서드를 분리한다면 더 좋은 효율을 보일 수 있을 것이다.

다음으로는 BFS 알고리즘을 활용한 역추적으로 간선을 제거한다.

    public static void removePathEdges() {
        boolean[] visited = new boolean[N];
        Queue<Integer> queue = new LinkedList<>();

        visited[D] = true;
        queue.offer(D);
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            for (int prev : parent.get(curr)) {
                graph[prev][curr] = INF;
                if (!visited[prev]) {
                    visited[prev] = true;
                    queue.offer(prev);
                }
            }
        }
    }

주의해야 할 점은 BFS에서 정점이 한 번 확장(expand)되었다는 것은, 해당 정점으로 향하는 모든 간선이 제거되었다는 의미이다. 그러므로 정점은 한 번만 확장되어도 된다는 점에 유념하자. visited 배열을 사용하지 않으면 메모리 초과가 발생한다.

3. Conclusion

역추적이라는 아이디어를 떠올리는 것이 어렵지도 않고, 구현이 난이도가 있는 편도 아니다. 내가 비교적 다른 알고리즘보다 그래프를 잘 풀어서 그런 것인지 플래티넘 문제라고는 생각되지 않았다.