[BaekJoon] 1865 웜홀 (Java)

1.  문제 링크

https://www.acmicpc.net/problem/1865

2.  문제

요약

• 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있습니다.
• 도로는 방향이 없으며 웜홀은 방향이 있습니다.
• 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 됩니다.
• 한 지점에서 출발을 해서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발하였을 때보다 시간이 되돌아가 있는 경우가 있는지 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 5보다 작거나 테스트케이스의 개수 TC가 주어지고 두 번째 줄부터 TC개의 테스트케이스가 주어집니다.
  • 테스트케이스의 첫 번째 줄에는 1보다 크거나 같고 500보다 작거나 같은 지점의 수 N, 1보다 크거나 같고 2,500보다 작거나 같은 도로의 개수 M, 1보다 크거나 같고 200보다 작거나 같은 웜홀의 개수 W가 주어집니다.
  • 두 번째 줄부터 M개의 줄에는 도로의 정보가 S, E, T 세 정수로 주어집니다. S와 E는 연결된 지점의 번호, T는 이 도로를 통해 이동하는데 걸리는 시간을 의미합니다.
  • M + 2번째 줄부터 M + W + 1번째 줄까지 웜홀의 정보가 S, E, T 세 정수로 주어지는데 S는 시작 지점, E는 도착 지점, T는 줄어드는 시간을 의미합니다.
    • T는 10,000보다 작거나 같은 자연수 또는 0입니다.
• 출력: TC개의 줄에 걸쳐 시간이 줄어들면서 출발 위치로 돌아오는 것이 가능하다면 YES, 불가능하다면 NO를 출력합니다.

3.  소스코드

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

public class Main {
    static StringBuilder sb = new StringBuilder();
    static Reader scanner = new Reader();
    static final int INF = 30000000;
    static int N, M, W;
    static Edge[] edges;
    static int[] weight;

    static void input() {
        N = scanner.nextInt();
        M = scanner.nextInt();
        W = scanner.nextInt();
        edges = new Edge[2 * M + W];
        for(int road = 0; road < M; road++) {
            int l1 = scanner.nextInt(), l2 = scanner.nextInt(), weight = scanner.nextInt();
            edges[2 * road] = new Edge(l1, l2, weight);
            edges[2 * road + 1] = new Edge(l2, l1, weight);
        }
        for(int worm = 2 * M; worm < 2 * M + W; worm++) {
            int start = scanner.nextInt(), end = scanner.nextInt(), weight = scanner.nextInt();
            edges[worm] = new Edge(start, end, weight * (-1));
        }
    }

    static void solution() {
        boolean isCycle = false;
        for(int loc = 1; loc <= N; loc++) {
            if(bellmanFord(loc)) {
                isCycle = true;
                sb.append("YES").append('\n');
                break;
            }
        }
        if(!isCycle) sb.append("NO").append('\n');
    }

    static boolean bellmanFord(int start) {
        weight = new int[N + 1];
        Arrays.fill(weight, INF);
        weight[start] = 0;
        boolean isChanged = false;

        loop:
        for(int loc = 1; loc <= N; loc++) {
            isChanged = false;
            for(Edge e : edges) {
                if(weight[e.start] == INF) continue;
                if(weight[e.end] > weight[e.start] + e.weight) {
                    weight[e.end] = weight[e.start] + e.weight;
                    isChanged = true;
                    if(loc == N) {
                        isChanged = true;
                        break loop;
                    }
                }
            }
            if(!isChanged) break;
        }
        return isChanged;
    }

    static class Edge {
        int start, end, weight;
        public Edge(int start, int end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }
    }

    public static void main(String[] args) {
        int TC = scanner.nextInt();
        while(TC-- > 0) {
            input();
            solution();
        }
        System.out.println(sb.toString());
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;
        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch(IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 도로와 웜홀을 나타내기 위해 Edge 클래스를 생성합니다.
  • 시작지점과 도착지점, 걸리는 시간을 멤버로 갖습니다.
  • 웜홀은 시간이 줄어들기 때문에 걸리는 시간을 나타낼 때 음수로 나타냅니다.
• 도로와 웜홀을 Edge 배열에 모두 담아 Bellman-Ford 알고리즘에 이용합니다.
• 각 노드를 시작점으로 하여 Bellman-Ford 알고리즘을 통해 시작점부터 다른 모든 지점까지의 최단 시간을 구하면서 음의 사이클이 발생하는지 확인하고 이를 통해 시간이 줄어드는 경우가 있는지 확인합니다.
  • 최단 시간 테이블인 weight의 값을 INF 값으로 초기화하고 시작지점의 값만 0으로 초기화합니다.
  • 모든 간선을 확인하여 각 간선을 거쳐 다른 지점으로 가는 시간을 계산하여 weight를 갱신합니다. 이 과정을 N - 1번 반복합니다.
  • 위 작업을 한 번 더 진행하는데, 만약 이 때 weight가 갱신된다면 음수 사이클이 존재하는 것입니다.
• 시간이 되돌아가는 경우를 구하는 것이기 때문에 음의 사이클이 존재하는 시작지점이 존재하는지 확인하고 만약 존재한다면 시간이 되돌아갈 수 있기 때문에 YES를 출력하고 그렇지 않다면 NO를 출력합니다.