[BOJ] 웜홀

문제

때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.)

웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다.

시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 궁금해졌다.

여러분은 백준이를 도와 이런 일이 가능한지 불가능한지 구하는 프로그램을 작성하여라.

풀이

그래프를 이용한 탐색을 진행해야한다.
도로로 가는 경우는 무향그래프로 양쪽으로 이동이 가능하지만 양수의 비용이 든다.
웜홀을 통해 가는 경우 유향그래프로 한쪽으로만 이동이 가능하지만 음수의 비용이 든다.

우리가 파악해야 하는 것은 어떠한 한 지점에 출발을 하여 원래 위치로 달아왔을 때, 출발 시점보다 시간이 더 이전이 되어야 한다.
도로를 이용해서 이동만 하면 양수의 시간이 흐르므로 이 조건이 불가능하다.
웜홀을 탄다면 음수 비용이 추가되므로 무조건적으로 웜홀을 이용하여 이동을 해야한다.

그런데 웜홀을 한번만 타면될까???
아니다. 1 -> 2 -> 3으로 가는 비용이 10이라고 하자.
그리고 3 -> 1로 가는 웜홀이 -3이라고 하자.
1 -> 2 -> 3 -> 1을 무한히 반복하여도 시간은 줄지 않는다.
3 -> 1로 가는 비용이 -11이라고 한다면??? 이때는 시간이 계속해서 줄어드는 것을 알 수 있다.
즉, 음수 사이클을 반복해야 출발지점보다 시간이 줄어드는 것을 알 수 있다.
따라서 벨만 포드 알고리즘을 이용해서 구현한다.

출발지가 정해진 것이 아니기때문에
N개의 정점을 모두 파악하는 것도 좋다.
그러나 음수 사이클 판별은 한개의 정점만으로도 파악할 수 있으므로 한개의 점점에서 벨만포드를 구현하는 것이 좋다.

import java.lang.*;
import java.io.*;
import java.util.*;

public class Main {
    static int[] distance;
    static int MAX = Integer.MAX_VALUE;
    static List<Node> list;
    static boolean flag;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int TC = Integer.parseInt(br.readLine());

        for (int i = 0; i < TC; i++) {
            String[] str = br.readLine().split(" ");
            int N = Integer.parseInt(str[0]);
            int M = Integer.parseInt(str[1]);
            int W = Integer.parseInt(str[2]);
            distance = new int[N + 1];
            list = new ArrayList<>();
            flag = false;

            for (int j = 0; j < M; j++) {
                str = br.readLine().split(" ");
                int a = Integer.parseInt(str[0]);
                int b = Integer.parseInt(str[1]);
                int cost = Integer.parseInt(str[2]);
                list.add(new Node(a, b, cost));
                list.add(new Node(b, a, cost));
            }

            for (int j = 0; j < W; j++) {
                str = br.readLine().split(" ");
                int a = Integer.parseInt(str[0]);
                int b = Integer.parseInt(str[1]);
                int cost = -Integer.parseInt(str[2]);
                list.add(new Node(a, b, cost));
            }

            bellmanFord(1, N, M, W);


            if (flag) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }

    static void bellmanFord(int start, int N, int M, int W) {
        distance[start] = 0;
        for (int i = 0; i < N - 1; i++) {
            for (int j = 0; j < list.size(); j++) {
                Node node = list.get(j);
                if (distance[node.start] == MAX) {
                    continue;
                }

                if (distance[node.end] > distance[node.start] + node.cost) {
                    distance[node.end] = distance[node.start] + node.cost;
                }
            }
        }

        for (int i = 0; i < list.size(); i++) {
            Node node = list.get(i);
            if (distance[node.start] == MAX) {
                continue;
            }

            if (distance[node.end] > distance[node.start] + node.cost) {
                flag = true;
                return;
            }
        }

    }

    static class Node {
        int start;
        int end;
        int cost;

        public Node(int start, int end, int cost) {
            this.start = start;
            this.end = end;
            this.cost = cost;
        }
    }

}

https://github.com/Win-9/Algorism/tree/main/BOJ/%EC%9B%9C%ED%99%80