[JAVA] 백준 2176 - 합리적인 이동경로 (Reverse Dijkstra + DP)

문제

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

2176번: 합리적인 이동경로

해결 방법

• 일단 이 문제는 문제 자체가 조금 헷갈리는 편이라고 생각함
• 점점 더 가까워져야 하는데 일직선 상에 있다면 이해가 쉽겠지만 그런것도 아니여서 정리할 필요가 있음
• 아래와 같은 예시가 있다고 가정해 보자 => 정답은 몇개일까??

• 1 -> 2로 갈 수 있는 방법은 총 6개
  1. [1->2]
  2. [1->3->4->5->2]
  3. [1->3->5->2]
  4. [1->4->5->2]
  5. [1->4->3->5->2]
  6. [1->5->2]
• 이 중 최단 경로는 [1->2] 단 하나 뿐임
• 하지만 정답은 3개 : [1->2], [1->3->5], [1->5->2]
• 왜냐하면 1->2까지의 최단거리는 3인데 [1->4 -> ... ->2] 처럼 가게 되면 4->2의 최단거리도 3이기 때문에 1->4는 합리적인 이동경로가 아니게 됨
• [1->3->5->2] 같은 경우에는 비록 최단거리는 아니지만 3->2의 최단 경로는 2이기 때문에 1->3은 갈 수 있음
• 문제를 이해했으면 이제 해결 방법을 생각해 보자
• 1->4와 같은 이동이 합리적인 이동경로가 아니라는 것을 바로 알 수 있도록 모든 노드에서 2까지의 최단 거리가 필요함
• 모든 노드 -> 노드 2까지의 최단거리를 알기 위해서 역방향 다익스트라 진행 ( https://chb2005.tistory.com/128 참고 )
• 이 과정을 마치면 dist = [3, 0, 2, 3, 1]이 구해짐
• 이제 DP를 진행해서 각 노드에서 2까지의 합리적인 이동경로 개수를 구해보자
• 최단거리가 짧은 노드부터 DP를 진행하면 됨
  • 만약 3번 노드에서 합리적인 이동경로를 구하려면 1번, 4번 노드에서 오는 것은 고려하지 않아야 되기 때문
• dp 배열에서 진행, dp[2] = 1로 초기화
  1. 최단 거리가 가장짧은 5번 노드부터 시작
  2. 5번 노드로 올 수 있는 노드는 1, 2, 3, 4가 있지만 이 중 최단거리가 5번 노드보다 짧은 노드는 2번 밖에 없음 => dp[5] = dp[2] = 1
  3. 다음으로 짧은 3번 노드
  4. 3번 노드로 올 수 있는 노드는 1, 4, 5가 있지만 이 중 최단거리가 3번 노드보다 짧은 노드는 5번 노드밖에 없음 => dp[3] = dp[5] = 1
  5. 다음으로 짧은 1, 4번 노드
  6. 1번 노드로 올 수 있는 노드는 2, 3, 4, 5가 있지만 이 중 최단거리가 1번 노드보다 짧은 노드는 2, 3, 5번이 있음 => dp[1] = dp[2] + dp[3] + dp[5] = 3
  7. 마찬가지로 dp[4] = dp[3] + dp[5] = 2
• 최종적으로 1 -> ... -> 2를 구해야 하기 때문에 dp[1]을 출력하면 됨
  • dfs로 시도해보려 했지만 시간초과 발생

코드

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

public class p2176 {
    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 m = Integer.parseInt(st.nextToken());   // 간선의 개수

        List<Node>[] connections = new List[n + 1];
        for(int i = 1 ; i <= n ; i ++) {
            connections[i] = new ArrayList<>();
        }

        for(int i = 0 ; i < m ; i ++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            // 양방향 연결
            connections[a].add(new Node(b, c));
            connections[b].add(new Node(a, c));
        }

        int[] dist = dijkstra(n, connections);
        int ans = dp(n, connections, dist);

        System.out.println(ans);
    }

    static int dp(int n, List<Node>[] connections, int[] dist) {
        // 2까지 가는 최단거리 기준으로 오름차순 정렬을 해야하기 때문에 PriorityQueue로 옮김
        PriorityQueue<PqFormat> distPq = new PriorityQueue<>();
        for(int i = 1 ; i <= n ; i ++) {
            distPq.add(new PqFormat(i, dist[i]));
        }
        distPq.poll();  // 2에서 2까지는 0이여서 맨 앞에 있을텐데, 2까지의 경로 가짓수는 1로 지정

        int[] dp = new int[n + 1];
        dp[2] = 1;

        while(!distPq.isEmpty()) {
            PqFormat now = distPq.poll();

            // 현재 노드와 연결되어 있는 노드 순회
            for(Node node : connections[now.index]) {
                // 현재 노드에 연결되어 있는 노드가 2까지 가는 최단경로가 짧다면
                // 연결되어 있는 노드의 가짓수를 모두 현재 노드에 더해줌
                if(dist[node.next] < dist[now.index]) {
                    dp[now.index] += dp[node.next];
                }
            }
            if(now.index == 1) {
                break;
            }
        }

        return dp[1];
    }
    static int[] dijkstra(int n, List<Node>[] connections) {
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[2] = 0;    // 문제에서 도착점은 2로 고정 => 역방향 다익스트라이기 때문에 2가 시작점이 됨

        boolean[] visited = new boolean[n + 1];

        PriorityQueue<PqFormat> pq = new PriorityQueue<>();
        pq.add(new PqFormat(2, 0));

        while(!pq.isEmpty()) {
            PqFormat now = pq.poll();
            if(visited[now.index] == true) continue;
            visited[now.index] = true;

            for(Node next : connections[now.index]) {
                // 다음 갈 곳의 dist값이 현재까지의 dist + 현재 위치에서 다음 갈 곳까지의 비용보다 크면 갱신
                if(dist[next.next] > dist[now.index] + next.cost) {
                    dist[next.next] = dist[now.index] + next.cost;
                    pq.add(new PqFormat(next.next, dist[next.next]));
                }
            }
        }

        return dist;
    }

    static class Node {
        int next, cost;

        public Node(int next, int cost) {
            this.next = next;
            this.cost = cost;
        }
    }

    static class PqFormat implements Comparable<PqFormat> {
        int index, dist;

        public PqFormat(int index, int dist) {
            this.index = index;
            this.dist = dist;
        }

        @Override
        public int compareTo(PqFormat o) {
            // dist 기준 오름차순 정렬
            return this.dist - o.dist;
        }
    }
}