백준 - 타임머신

문제 링크 ▶︎ 타임머신

문제 파악

문제에서 노드 사이의 간선의 cost가 음수가 존재한다고 했기 때문에 그냥 value를 우선순위큐에 넣어서 작은 cost의 간선으로 확장해나가는 것은 어렵다.
그리고 "시간을 무한히 오래 전으로 되돌릴 수 있다"는 말이 있는데 이건 간선의 순환을 했을 때, 계속해서 -계산이 되는 것을 찾으라는 말로 해석했다.
문제에 대한 이해도 쉽지 않았는데 구현도 어렵게 느껴지는 문제라서 우선 완전탐색을 한다는 생각으로 순회했다.

접근 방법

1. 노드와 간선은 해시맵에 밸류를 list로 만들어서 넣었다. 그리고 1에서 출발해서 몇번 도시에 도착하는 시간을 측정하기 위해서 long 배열을 만들었고, long으로 만든 이유는 최대한 MAX_VALUE를 크게 만들기 위해서이다.

2. 전체 간선의 수가 n-1개이기 때문에 한번 순회를 했을 때는 1번 도시에서 이웃한 2번 도시만 탐색하기 때문에 1번 도시에서 n번 도시까지 가는 경로를 모두 탐색하려면 n-1의 순회를 더 돌아줘야한다.

3. 그렇게 시간을 저장하는 data 배열을 모두 갱신하고 나서는 한번의 갱신문을 더 도는데 그 이유는 음수의 간선에 대한 사이클이 있는지를 탐색하기 위해서이다. 한번 돌면서 밸류가 더 낮아지는 현상, 즉 이미 다 갱신되었는데도 더 갱신된다는 것은 음수 사이클로 인해서 점점 낮아진다는 것을 의미하므로 그때는 바로 -1을 출력하고 리턴한다.

4. 그게 아니라면 모든 경로에 따른 시간을 출력해주고 방문하지 못한 곳은 -1을 출력해준다.

코드 구현

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        Map<Integer, List<int[]>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(i+1, 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.get(a).add(new int[] {b, c});
        }
        long[] data = new long[n+1];

        Arrays.fill(data, Long.MAX_VALUE);
        data[1] = 0;

        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= n; j++) {
                if (data[j] == Long.MAX_VALUE) {
                    continue;
                }
                for (int[] next : map.get(j)) {
                    int dest = next[0];
                    int cost = next[1];
                    if (data[dest] > data[j] + cost) {
                        data[dest] = data[j] + cost;
                    }
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            if (data[i] == Long.MAX_VALUE) {
                continue;
            }
            for (int[] now : map.get(i)) {
                int dest = now[0];
                int cost = now[1];
                if (data[dest] > data[i] + cost) {
                    System.out.println(-1);
                    return;
                }
            }
        }

        for (int i = 2; i <= n; i++) {
            if (data[i] == Long.MAX_VALUE) {
                System.out.println(-1);
            } else {
                System.out.println(data[i]);
            }
        }
    }
}

개선 사항

다익스트라처럼 풀지 못해서 완전탐색st로 풀었는데 벨만포드 알고리즘처럼 될 줄은 몰랐다. 이 기회에 벨만포드 알고리즘에 대해서 공부해야겠다. 그리고 음수 사이클을 찾는 더 좋은 방법이 있는지 공부해야한다.