[백준 1865 : JAVA] 웜홀/ 벨만-포드

개요

 

문제를 읽어보면 음의 가중치가 있는 그래프에서 

음의 사이클의 여부를 확인하는 문제라는 것을 알 수 있다.

(음의 사이클이란 경로를 지날 때마다 계속 최단거리가 감소하는 것을 뜻한다.)

 

위와 같은 그래프가 있을 때, 1 ▶ 1 최단거리가 -4 ▶ -8 ▶ - 12 ▶ -16....로 점점 줄어들게 되는데 이러한 경우를 음의 사이클이 있다고 한다.(음의 사이클은 최단거리를 구할 때 가중치에 음수가 있을 때 발생 가능성을 가지고 있다.)

 

음의 가중치가 있는 경우 다익스트라와 벨만 포드 중 벨만-포드 알고리즘을 선택해야 한다.

또한 벨만 포드 알고리즘은 음의 사이클의 여부를 확인할 수 있다.

 

문제

 

때는 2020년, 백준이는 월드나라의 한 국민이다. 월드 나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다.

시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 궁금해졌다. 여러분은 백준이를 도와 이런 일이 가능한지 불가능한지 구하는 프로그램을 작성하여라.

 

입력

 

풀이

 

총 v개의 노드가 있고 e개의 간선이 있다면,

 

|v - 1|번 e개의 간선에 대해 dist[]를 갱신해준다.

 

그러고 나서 1번 e개의 간선에 대해 dist[]를 갱신하려고 할 때 갱신이 된다면 음의 사이클이 있다는 뜻이다.

 

코드

 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    // 길 정보를 저장하기 위한 클래스
    // static으로 선언한 이유는 단지 편리함을 위해서.
    static class Road{
        // 출발노드
        int start;
        // 도착노드
        int end;
        // 걸리는 시간
        int cost;

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

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private static final int INF = 500 * 10_000;
    static int n, m, w;
    static Road[] roads;
    static int[] dist;

    public static void main(String[] args) throws IOException {
        int testCnt = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        // 테스트 개수만큼 반복
        for(int i = 0 ; i < testCnt; i++){
            // 입력값을 변수에 초기화한다.
            init();
            // 음수 사이클이 있는 경우
            if(bellmanFord())
                sb.append("YES\n");
            // 음수 사이클이 없는 경우
            else
                sb.append("NO\n");
        }

        bw.write(sb.toString());

        br.close();
        bw.close();
    }

    private static void init() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        w = Integer.parseInt(st.nextToken());

        dist = new int[n + 1];
        roads = new Road[2 * m + w];

        // roads[]의 인덱스를 나타낸다.
        int index = 0;

        for(int i = 0 ; i < m + w; i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            // 무방향이기 때문에 반대방향도 추가한다.
            if(i < m){
                roads[index++] = new Road(start, end, cost);
                roads[index++] = new Road(end, start, cost);
            // 웜홀은 유방향이기 때문에 시간만 * -1 해주어서 추가한다.
            }else{
                roads[index++] = new Road(start, end, cost * -1);
            }
        }
    }

    private static boolean bellmanFord(){
        // dist배열을 INF로 초기화
        Arrays.fill(dist, INF);
        // 시작점을 1번 노드로 지정하고 dist[1]값을 0으로 초기화
        dist[1] = 0;

        // v - 1번 relax해준다.
        for (int i = 1; i < n; i++) {
            // edge개수 만큼 확인을 한다.
            for (int j = 0; j < roads.length; j++) {
                Road road = roads[j];

                if (dist[road.start] != INF && dist[road.start] + road.cost < dist[road.end]){
                    dist[road.end] = dist[road.start] + road.cost;
                }
            }
        }

        // 음수 사이클 유무 판정
        for(int i = 0 ; i < roads.length; i++){
            Road road = roads[i];
            // 갱신이 또 된 경우
            if (dist[road.start] != INF && dist[road.start] + road.cost < dist[road.end])
                return true;
        }

        // 갱신이 되지 않고 for문을 빠져나온 경우
        return false;
    }
}