백준 Gold2 2176 합리적인 이동 경로

문제 링크

문제 설명

시작점 S, 끝점 T에 해당하는 그래프 상의 모든 경로 중 이동했을 때 거리가 짧아지는 경로의 수를 구하는 문제이다. S와 T는 각각 1, 2로 고정되어 있다.

문제 설명에 맞춰 예제 입력에 대해 살펴보자

1에서 2까지 최소 거리는 3이다. 당연히 이 거리를 기준으로 보면 최단 경로를 제외하곤 합리적인 이동 경로가 없는 것처럼 보인다. 하지만 여기서 3으로 이동한다고 생각해보자. 원래 거리는 3이었으나, 3으로 이동하면서 거리가 2로 줄었으니 합리적인 이동 경로에 해당한다.

즉, 조건으로 나타내면 아래와 같다.

D(x, y) = x, y 사이의 거리
정점 S에서 X로 이동할 때,
합리적인 이동경로 = dist(S, T) > dist(X, T) 일 때, Edge(S, X)는 합리적인 이동경로이다. 

한마디로 현재 위치한 정점에서 인접한 정점 사이의 거리는 무시해야한다는 소리이다.

문제 풀이

합리적인 이동 경로에 대한 정의를 이해했다면 80%이상 푼 문제이다. 우선 도착점인 T, 그러니까 2번 정점에서 다른 정점까지 도달하는 거리를 먼저 구해야한다. 여기서는 다익스트라 알고리즘을 이용할 수 있다.

그 후, 거리가 가장 짧은 노드부터 탐색을 해서 해당 노드(X)의 인접 노드(Y)들에서 T까지의 거리가 dist(X, T) < dist(X, Y) 라면 거리가 짧아지는 것이므로 Y의 합리적인 이동 경로 수에 X의 합리적인 이동 경로 수를 더해주면 된다.

의사코드로 작성하면 아래와 같다.

let adj[] = Edges of Vertex V 
let minDist = dijik(2);
let minIndex = [1...n(V)]
sort(minIndex, (a, b)->(minDist[a] - minDist[b]))

let dstIndex = i, i is index of value 2 in minIndex;

routeCount= [0] * n(V+1) 
routeCount[2] = 1;

for current in minIndex :
    continue if current is 0 or 2
    
    edges = adj[i]  
    for next in range(0, edges.length) :
        if dist[next] < dist[current] : 
            routeCount[i] += routeCount[j];
 
return routeCount[1]

가 된다.

예를들어 위 예에서는 가장 거리가 짧은 노드가 4번 노드이고 거리는 1이다. 4번 노드에 인접한 노드들은 1번 노드와 2번 노드인데 2번 노드는 거리가 0이므로 dist[4] > dist[2] 가 성립한다. 따라서 routeCount[4] += routeCount[2] 가 되어 만족하는 합리적인 경로가 1이된다. 다음으로 짧은 거리는 3번 노드인데 3번 노드의 인접 노드는 1번과 2번이다. 마찬가지로 2번에 의해 routeCount[3] = 1이 된다. 1번 노드에서는 4번 3번 노드로 가면 모두 합리적인 경로이므로 routeCount[1] = routeCount[4] + routeCount[3] 가 되어 2가 출력된다.

소스코드

import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.*;
import java.util.stream.IntStream;
import java.io.*;

public class Main {
    static void run() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        new Solution(reader).run();
        reader.close();
    }

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

class Solution {

    public static class Edge {
        int to;

        int weight;

        public Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    int nrVertex;

    int nrEdge;

    List<List<Edge>> adj = new ArrayList<>();
        
    public Solution(BufferedReader reader) throws IOException {
        String[] line =reader.readLine().split(" ");
        nrVertex = Integer.parseInt(line[0]);
        nrEdge = Integer.parseInt(line[1]);

        adj = new ArrayList<>(nrVertex+1);
        for(int i = 0 ; i <= nrVertex ; i++){
            adj.add(new ArrayList<>());
        }

        int from, to, weight;

        for(int i = 0 ; i < nrEdge ; i++) {
            line = reader.readLine().split(" ");
            from = Integer.parseInt(line[0]);
            to = Integer.parseInt(line[1]);
            weight = Integer.parseInt(line[2]);
            adj.get(from).add(new Edge(to, weight));
            adj.get(to).add(new Edge(from, weight));
        }
    }

    public int[] dijik(int from) {
        int[] dists = new int[nrVertex + 1]; // from에서 [i]로 가는 최소 거리
        boolean[] visited = new boolean[nrVertex+1];

        Arrays.fill(dists, Integer.MAX_VALUE);
        PriorityQueue<Edge> pq = new PriorityQueue<>((a, b) -> a.weight-b.weight);

        pq.add(new Edge(from, 0));
        dists[from] = 0;

        while(!pq.isEmpty()) {
            Edge cur = pq.poll();

            if(cur.weight > dists[cur.to]) continue;
            if(visited[cur.to]) continue;
            visited[cur.to] = true;
            
            List<Edge> edges = adj.get(cur.to);

            for(int i = 0 ; i < edges.size() ; i++) {
                Edge nxt = edges.get(i);
                int nxtDist = dists[cur.to] + nxt.weight;
                
                if(nxtDist > dists[nxt.to]) continue;
                dists[nxt.to] = nxtDist;
                pq.add(new Edge(nxt.to, nxtDist));
            }
        }

        return dists;
    }

    public void run() {
        int answer = 0;

        // 끝점에서 모든 점으로 가는 거리를 구한다.
        int[] minDists = dijik(2);
        Integer[] indices = IntStream.rangeClosed(0, nrVertex)
                            .boxed()
                            .toArray(Integer[]::new);

        Arrays.sort(indices, (a, b)->minDists[a]-minDists[b]);
        
        int[] memo = new int[nrVertex+1];
        memo[2] = 1;
        // 거리가 가장 짧은 노드부터 탐색한다.

        for(int i = 0 ; i < nrVertex ; i++) {
            if(indices[i] == 2 || indices[i] == 0) continue;
            int cur = indices[i];
            List<Edge> edges = adj.get(indices[i]);

            for(Edge edge : edges) {
                if(minDists[edge.to] >= minDists[cur]) continue;
                memo[cur] += memo[edge.to];
            }
        }


        System.out.println(memo[1]);
    }
}

후기

문제에서 말하는 합리적인 경로의 정의를 이해를 못해서 5분 정도 헤멨다. 설명이 모호한건지 내가 이해를 잘 못하는건지 모르겠는데 문제 자체는 굉장히 쉬운 편에 속한다. 골드2로 배정될 문제인지 의문점이 든다.