[Baekjoon] 2176: 합리적인 이동경로

문제

문제를 읽자마자 머리를 붙잡았다. 설명이 참,,, 심오하다,,

,,,?

풀이나 알아보자.

 

풀이

내 풀이

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

public class Q2176 {
    private static final List<List<int[]>> graph = new ArrayList<>();
    private static long[] weights;
    private static int[] counts;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        weights = new long[n + 1];
        counts = new int[n + 1];
        Arrays.fill(weights, Integer.MAX_VALUE);

        int m = Integer.parseInt(input[1]);
        for (int i = 0; i < m; i++) {
            String[] edge = br.readLine().split(" ");
            int e1 = Integer.parseInt(edge[0]);
            int e2 = Integer.parseInt(edge[1]);
            int w = Integer.parseInt(edge[2]);
            graph.get(e1).add(new int[] { e2, w });
            graph.get(e2).add(new int[] { e1, w });
        }

        setDestWeight(new long[] { 2, 0 }); // 2에서 1로 가는 가중치를 세팅해준다. 왜 why? 합리적인 이동경로란 이동을 했을 때 가중치가 더 줄어드는 경로로 가야되기 때문이다.

        counts[2] = 1;
        System.out.println(search(1));
    }

    public static void setDestWeight(long[] start) {
        Queue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(v -> v[1]));
        pq.offer(start);
        weights[(int) start[0]] = 0;

        while (!pq.isEmpty()) {
            long[] cur = pq.poll();
            int curVertex = (int) cur[0];
            long curWeight = cur[1];

            if (weights[curVertex] < curWeight) {
                continue;
            }

            for (int[] next : graph.get(curVertex)) {
                int nextVertex = next[0];
                int nextWeight = next[1];

                if (weights[nextVertex] > weights[curVertex] + nextWeight) {
                    pq.offer(new long[] { nextVertex, weights[curVertex] + nextWeight });
                    weights[nextVertex] = weights[curVertex] + nextWeight;
                }
            }
        }
    }

    public static int search(int cur) {
        if (counts[cur] != 0) { // 탐색됐으면 리턴
            return counts[cur];
        }

        for (int[] next : graph.get(cur)) {
            if (weights[cur] > weights[next[0]]) { // 다음 길에서부터 목적지로 가는 가중치가 더 줄어드는 경우 탐색한다.
                counts[cur] += search(next[0]);
            }
        }
        return counts[cur];
    }
}

위 주석들의 설명을 보충하자면,

여기서 빨간 숫자는 목적지까지의 최소 가중치를 의미한다.

 

문제가 무조건 1에서 출발한다 했으므로 1에서 출발해보자. 그러면 3과 4의 선택지가 있다.

3으로 이동했을 경우, 이동해도 1에서의 목적지까지 최소 가중치인 3보다 줄어들지 않으므로 합리적인 경로가 아니다.

4로 이동했을 경우, 목적지까지 가중치가 2이므로 줄어드는 것을 확인할 수 있다.

 

따라서 합리적인 경로는 1이 된다.

 

이해가 아직 가지 않는가? 괜찮다 원래 인생이 그런거다.

 

회고

이 문제를 보고 바로 이해할 수 있는 머리를 길러야겠다.