[백준] 14554번 The Other Way

문제 설명

• https://www.acmicpc.net/problem/14554
• Gold 1
• 소요 시간 : 30분

문제 풀이

• 다익스트라 알고리즘과 DFS를 사용해 풀이하였다.
• 우선 다익스트라 알고리즘을 이용해 S노드와 다른 노드 간의 최단거리를 모두 구해준다.
• DFS를 이용해 Top-down방식으로 E노드부터 시작해서 S노드까지 이동하며 DP테이블을 업데이트 시켜준다. (이 때, dist배열의 값을 통해 최단거리 경로일 경우에만 다음 노드로 이동)

소스 코드 (JAVA)

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

public class Main {
    static class Point implements Comparable<Point>{
        int n;
        long d;

        public Point(int n, long d) {
            this.n = n;
            this.d = d;
        }

        @Override
        public int compareTo(Point o) {
            if (this.d > o.d) return 1;
            else return -1;
        }
    }
    static int N, M, S, E;
    static List<Point>[] map;
    static long MOD = 1000000009L;
    static long[] dist;
    static long[] dp;

    // S에서 n까지 오는 최단 거리 경로 개수
    static long dfs(int n) {
        //기저 조건
        if (n == S) return 1;
        if (dp[n] != -1) return dp[n];
        long result = 0;
        for (Point next : map[n]) {
            if (dist[next.n] + next.d != dist[n]) continue;
            result = (result + dfs(next.n)) % MOD;
        }
        return dp[n] = result;
    }

    static void solve() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        dist = new long[N+1];
        dp = new long[N+1];
        map = new List[N+1];
        Arrays.fill(dist, Long.MAX_VALUE);
        Arrays.fill(dp, -1);
        for (int i = 0; i <= N; i++)
            map[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());
            map[a].add(new Point(b, c));
            map[b].add(new Point(a, c));
        }

        // 1. 다익스트라 진행
        PriorityQueue<Point> pq = new PriorityQueue<>();
        pq.add(new Point(S, 0));
        dist[S] = 0;

        while(!pq.isEmpty()) {
            Point cur = pq.poll();
            if (dist[cur.n] < cur.d) continue;
            for (Point next : map[cur.n]) {
                int nNode = next.n;
                long nDist = next.d + cur.d;
                if (nDist < dist[nNode]) {
                    dist[nNode] = nDist;
                    pq.add(new Point(nNode, nDist));
                }
            }
        }

        // 2. DFS 진행
        bw.write(dfs(E) + "\n");

        bw.flush();
    }

    public static void main(String[] args) throws IOException {
        solve();
    }
}

/**
 * The Other Way (15:50)
 *
 * N : 노드 개수       ( N <= 10만 )
 * M : 영방향 간선 개수  ( M <= 30만 )
 *
 * - S -> E로 가는 최단 경로의 개수
 *
 * - 다익스트라 응용
 * - 다익스트라로 S부터 모든 노드까지 최단 거리를 구함
 * - 이후 DFS를 통해 TOP-DOWN DP를 사용하여 해당 최단 거리 루트를 만족하는 모든 경우의 수 구해줌
 *
 * N M S E
 * A B C
 * ...
 */