[Java] BaekJoon 2176. 합리적인 이동경로(골드2) (Dijkstra,DP)

문제 출처: https://www.acmicpc.net/problem/2176

2176번: 합리적인 이동경로

 

문제 이해 

 

목표

그래프 상에서 1번노드에서 2번노드로 가는 경로 중 
계속해서 가까워지는 경로만 count해서 개수를 출력하시오.

풀이

 

처음 고안한 풀이

1. 2번노드를 출발노드로 1번노드를 도착노드로 설정한 dijkstra알고리즘 실행
2. 1번노드에서 출발하여 2번노드까지 도착하는 dfs 중 
    dfs 할 때 계속해서 가까워지는 경로의 개수를 count 

=> 정답 일치 ! 그러나 시간초과 !

두번째 고안한 풀이
1. 위의 1과 같음
2(중요). -> 1의 dijkstra를 진행할 때 
       (현재 노드까지의 price < 다음 노드까지의 price) 인 경우, 
       다음 dp에 지금까지의 경로 수만큼 +해줌
       -> dp[nextEdge.dest] += dp[current];
3. dp[1]출력 (dijkstra를 역으로 진행했기 때문에 도착노드인 1을 출력)

 

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

public class 합리적인이동경로 {
    private static int N;
    private static int M;
    private static int answer;
    private static ArrayList<Edge>[] adjList;
    private static int[] minPrice;

    static class Edge implements Comparable<Edge> {
        int dest;
        int price;

        public Edge(int dest, int price) {
            this.dest = dest;
            this.price = price;
        }

        @Override
        public int compareTo(Edge o) {
            return this.price - o.price;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strArr = br.readLine().split(" ");
        N = Integer.parseInt(strArr[0]);
        M = Integer.parseInt(strArr[1]);
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        // adjList 만들기
        adjList = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            adjList[i] = new ArrayList<>();
        }
        for (int i = 0; i < M; i++) {
            strArr = br.readLine().split(" ");
            int start = Integer.parseInt(strArr[0]);
            int dest = Integer.parseInt(strArr[1]);
            int price = Integer.parseInt(strArr[2]);
            adjList[start].add(new Edge(dest, price));
            adjList[dest].add(new Edge(start, price));
        }

        // Dijkstra -> 출발 2번노드 도착 1번노드
        minPrice = new int[N + 1];
        Arrays.fill(minPrice, Integer.MAX_VALUE);
        minPrice[2] = 0;
        int[] dp = new int[N + 1];
        dp[2] = 1;
        pq.add(new Edge(2, 0));
        while (!pq.isEmpty()) {
            Edge nowEdge = pq.poll();
            int current = nowEdge.dest;
            // 최단거리가 아니라면 스킵
            if (minPrice[current] < nowEdge.price) {
                continue;
            }
            // 기존의 최소비용보다 더 저렴하다면 교체합니다.
            for (Edge nextEdge : adjList[current]) {
                int nextDistance = minPrice[current] + nextEdge.price;
                if (minPrice[nextEdge.dest] > nextDistance) {
                    minPrice[nextEdge.dest] = nextDistance;
                    pq.add(new Edge(nextEdge.dest, nextDistance));
                }
                // 교체하지 않아도.. 현재 노드의 값보다 다음노드의 값이 크다면 경로가 있는거니까 count++ (dp)
                if (minPrice[nextEdge.dest] > minPrice[current]){
                    dp[nextEdge.dest] += dp[current];
                }
            }
        }
//        dfs로 합리적인 이동경로 찾기 -> 시간초과로 실패
//        dfs(1); // -> 시간초과
        answer = dp[1];

        System.out.println(answer);

    }

//    private static void dfs(int start) {
//        for (Edge edge : adjList[start]) {
//            int next = edge.dest;
//            if(next == 2){
//                answer++;
//                continue;
//            }
//            if (minPrice[start] > minPrice[next]) { // 더 다음 노드가 2에 더 가까우면
//                dfs(next);
//            }
//        }
//    }
}

 

결과

 

다익스트라 정리

이해: 출발노드를 기준으로 모든 노드들에 도착하는 최단경로를 갱신하는 것.

-> 그래프로 map으로 구현하면, 노드들을 기준으로 최단경로 탐색하는 것이기 때문에 
    시작노드와 끝노드를 제외한 나머지 노드들의 갱신-> n-2번
    방문하지 않은 노드들 중 가장 최소 edge를 찾는것 -> n번
   => O(n제곱)의 시간복잡도가 나옴 

-> 인접리스트로 구현하면, 배열의 인덱스는 현재 위치의 노드, 배열의 값은 간선의 정보(도착지점, 비용)
    으로 해서 인접리스트를 만들고, 우선순위 큐를 구현하여 출발 노드에서 시작하는 dijkstra를 만듬
    간선의 정보로 탐색을 할때 간선개수만큼, 그리고 우선순위큐(Heap)로 제일 적은 노드를 찾을 수 있음 -> NlogN 

인접리스트로 다익스트라 만들기

1. 인접리스트를 만들고, 간선을 이용한 dijkstra를 진행할 PriorityQueue를 만든다. 
2. 출발노드에서 출발노드로 도착하는 간선(비용은 0)을 pq에 담고 탐색을 진행한다. 
   d[모든노드] = MAX으로 초기화
   d[출발노드] = 0
3. 탐색

 현재 노드 <- 큐에서 비용이 제일 적은 하나의 노드를 거냄
(1) 현재노드로 가는 비용(nowEdge.price)이, 기존의 현재노드 비용(d[출발노드])보다 크면 continue 

(2) 인접리스트를 통해 현재노드와 연결된 간선(다음노드)들로 탐색 - iter 

        d[다음노드] > d[현재노드] + 다음노드비용(next.price) 이면 
        d[다음노드] = d[현재노드] + 다음노드비용 으로 갱신
        그리고 PriorityQueue에 다음노드로 가는 Edge담음