문제

이해

버스는 단방향 간선을 의미합니다.

버스가 이동할때 그냥 이동, 순간이동, 시간을 되돌아가기를 할 수 있습니다. 각각의 시간 가중치는 양수, 0, 음수를 의미하기도 합니다.

1번 도시에서 다른 도시까지의 최단거리를 구합니다. 도달할 수 없는 경우 -1로 출력합니다. 단, 시간을 무한적으로 되돌릴 수 있다면 -1 하나만을 출력합니다.

접근

문제를 단순하게 생각하면 단방향 그래프 상에서 가중치가 +, 0, -이 존재합니다.

1번부터 다른 노드까지 최단거리가 존재한다면 그대로 출력, 없다면 -1, 애초에 최단거리가 -로 계속 갱신된다면 -1을 출력해야 합니다.

최단거리가 -로 갱신된다는 말은 음의 가중치 간선을 돌고 돈다는 의미이고 즉, 그래프 상에서 음의 사이클이 존재한다는 의미입니다.

최단거리를 구하는 알고리즘에는 데이크스트라, 벨만포드, 플로이드워셜이 있습니다. 플로이드워셜은 모든 노드간의 최단거리를 구하고 데이크스트라와 벨만포드는 특정 노드를 기준으로 최단거리를 구합니다.

하지만 데이크스트라는 양의 간선만 있는 그래프에서 적용할 수 있습니다. 반면, 벨만포드는 음의 가중치가 포함된 그래프에서 최단거리를 구할 수 있습니다. 벨만포드에서는 최단거리를 구하면서 음의 사이클이 존재하는지의 여부도 판단할 수 있습니다.

본 문제에서는 단순 벨만포드를 수행하고 결과에 따라서 값을 출력하면 되겠습니다.

풀이

private static boolean BellMan() {
        minDistance[1] = 0;

        for (int i = 1; i < N; i++) {
            for (Edge cur : edgeList) {
                if(minDistance[cur.from] >= INF){
                    continue;
                }
                long dist = minDistance[cur.from] + cur.weight;

                minDistance[cur.to] = Math.min(minDistance[cur.to], dist);
            }
        }

        for (Edge cur : edgeList) {
            if(minDistance[cur.from] >= INF){
                continue;
            }
            long dist = minDistance[cur.from] + cur.weight;

            if (minDistance[cur.to] > dist) {
                return true;
            }
        }

        return false;
    }

벨만포드는 모든 간선을 노드의 개수만큼 탐색하며 최단거리를 갱신합니다. 시간복잡도는 따라서 VxE가 됩니다.

음의 사이클이 없는 경우에는 모든 과정이 끝났을 때 최단거리가 갱신되지 않습니다. 벨만포드에서는 V만큼 탐색을 한 뒤 마지막 1번을 더 탐색해 만일 최단거리가 갱신되면 음의 사이클이 존재한다고 판단합니다.

전체 코드

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class prob11657 {
    static final int INF = 1_000_000_000;

    static class Edge {
        int from;
        int to;
        int weight;

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

    }

    static int N, M;
    static long[] minDistance;
    static List<Edge> edgeList;
    static StringTokenizer st = null;
    static StringBuilder sb = new StringBuilder();

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

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        edgeList = new ArrayList<>();
        minDistance = new long[N + 1];
        Arrays.fill(minDistance, INF);

        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());

            edgeList.add(new Edge(A, B, C));
        }

        if (BellMan()) {
            System.out.println(-1);
        } else {
            for (int i = 2; i <= N; i++) {
                if (minDistance[i] == INF) {
                    sb.append(-1);
                } else {
                    sb.append(minDistance[i]);
                }
                sb.append("\n");
            }
        }

        System.out.println(sb.toString());
    }

    private static boolean BellMan() {
        minDistance[1] = 0;

        for (int i = 1; i < N; i++) {
            for (Edge cur : edgeList) {
                if(minDistance[cur.from] >= INF){
                    continue;
                }
                long dist = minDistance[cur.from] + cur.weight;

                minDistance[cur.to] = Math.min(minDistance[cur.to], dist);
            }
        }

        for (Edge cur : edgeList) {
            if(minDistance[cur.from] >= INF){
                continue;
            }
            long dist = minDistance[cur.from] + cur.weight;

            if (minDistance[cur.to] > dist) {
                return true;
            }
        }

        return false;
    }
}

결과

리뷰

단순히 벨만포드의 개념을 물어보는 문제였습니다.