백준 - 1865 웜홀(Java)

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

1865번: 웜홀

 

벨만-포드 문제입니다.

벨만-포드 알고리즘은 음의 가중치가 있을 때, 최소 거리를 구하기 위해 사용됩니다.

만약, 양의 가중치만이 있을 때 사용되는 다익스트라와 대조됩니다.

벨만-포드는 노드 n개가 있을 때, n-1 번 거리를 갱신한 후에 한 번 더 갱신합니다.

만약 한 번더 갱신이 되면 음의 사이클이 존재하는 것입니다.

이 문제의 경우 음의 사이클이 발생하는지 확인하기 위해 벨만-포드 알고리즘을 사용하게 됩니다.

 

문제는 노드 n개의 그래프에서 음의 사이클이 발생하는지, 안하는지 구하는 문제입니다.

음의 사이클이면 YES를 출력하고, 음의 사이클이 아니면 NO를 출력합니다.

간선은 두 가지 종류가 있습니다.

• m개의 도로(양의 가중치, 무방향 간선)
• w개의 웜홀(음의 가중치, 단방향 간선)

 

각 테스트 케이스 첫 줄에 n, m, w가 주어졌을 때, m개의 도로 정보와 w개의 웜홀 정보가 주어집니다.

해당 정보를 저장하여 벨만-포드 알고리즘을 구현하면 끝나는 문제입니다.

 

 

[구현 코드]

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

public class Main {
    private static final int MAX = 1_000_000_000;
    private static List<List<Node>> roads;

    private static class Node {
        int e, w;

        public Node(int e, int w) {
            this.e = e;
            this.w = w;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stz;

        int testCase = Integer.parseInt(br.readLine());
        while (testCase-- > 0) {
            stz = new StringTokenizer(br.readLine(), " ");

            int n = Integer.parseInt(stz.nextToken());
            int m = Integer.parseInt(stz.nextToken());
            int w = Integer.parseInt(stz.nextToken());

            roads = new ArrayList<>();

            for (int i = 0; i < n + 1; i++) {
                roads.add(new ArrayList<>());
            }

            // 도로
            for (int i = 0; i < m; i++) {
                stz = new StringTokenizer(br.readLine(), " ");
                int s = Integer.parseInt(stz.nextToken());
                int e = Integer.parseInt(stz.nextToken());
                int t = Integer.parseInt(stz.nextToken());

                roads.get(s).add(new Node(e, t));
                roads.get(e).add(new Node(s, t));
            }

            // 웜홀
            for (int i = 0; i < w; i++) {
                stz = new StringTokenizer(br.readLine(), " ");
                int s = Integer.parseInt(stz.nextToken());
                int e = Integer.parseInt(stz.nextToken());
                int t = Integer.parseInt(stz.nextToken());

                roads.get(s).add(new Node(e, t * (-1)));
            }

            boolean isPossible = bellmanFord(n);
            String answer = isPossible ? "YES" : "NO";
            bw.write(answer + System.lineSeparator());
        }

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

    private static boolean bellmanFord(int n) {
        int[] distance = new int[n + 1];
        Arrays.fill(distance, MAX);
        distance[1] = 0;
        boolean isUpdated = false;

        // n-1번
        for (int i = 1; i < n; i++) {
            isUpdated = false;

            for (int j = 1; j < n + 1; j++) {
                for (int k = 0; k < roads.get(j).size(); k++) {
                    Node nn = roads.get(j).get(k);
                    if (distance[nn.e] > distance[j] + nn.w) {
                        distance[nn.e] = distance[j] + nn.w;
                        isUpdated = true;
                    }
                }
            }

            if (!isUpdated) break;
        }

        // n-1번 갱신이 되었으면, 한 번더 갱신 진행(음의 사이클 확인)
        if (isUpdated) {
            for (int j = 1; j < n + 1; j++) {
                for (int k = 0; k < roads.get(j).size(); k++) {
                    Node nn = roads.get(j).get(k);
                    if (distance[nn.e] > distance[j] + nn.w) {
                        return true;
                    }
                }
            }
        }

        return false;
    }
}