[BOJ] 백준 [1865] 웜홀 JAVA

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

1865번: 웜홀

[문제]

[풀이]

이 문제에 접근하기 위해서 벨만-포드 알고리즘을 사용해야 한다.
최단거리 알고리즘인 다익스트라는 음의 가중치를 가지고 사이클이 있을 경우 무한순회를 하면
끝 없이 최단경로를 음의 무한대로 갱신 시킬 수 있기 때문

여기서 중요한점 => 아무 정점에서 시작해도 음의 사이클을 찾을 수 있다

이게 무슨말이냐면 평소에 다익스트라를 쓸 때 항상 쓰던 거리배열
Distance[정점의크기n] <- 이 배열을 처음에 Intger.MaxValue 로 초기화를 한 후
탐색 시작 정점 (start) 부분은 0으로 초기화 하여 Distance[start] = 0 인 상태로 시작했다

하지만 잘 생각해보면 그 어떤 정점에서 시작을 하여도 음의 사이클을 탐지 가능하다.

예를 하나 들어보면 1, 2, 3, 4 그 어떤 정점에서 시작해도 만약 5,6,7 .... 등 저 구간에 음의 사이클이 존재하면
Distance 거리 배열을 갱신하는 과정에서 탐지가 된다.

다익스트라를 사용했을 땐 (정점의 개수-1) 만큼 순회를 돌려서 모든 최단거리를 구할 수 있다면
여기서 한번 더 탐색을 했을 때 또 갱신이 된다 ? => 음의 사이클이 존재한다 라는 결론이 나옴
따라서 Distance 거리 배열 처음 초기화를 Integer.MaxValue 가 아닌 0 으로 해야한다

순회 횟수는 정점의 개수(n) 만큼 순회를 하고 정점 1~n 과 인접한 노드들 하나씩 조사를 하는 과정 중에
거리 갱신이 되지 않는다 => 음의 사이클이 없다
그 외의 경우 => 음의 사이클이 있는 경우이다.

import java.util.stream.*;

import static java.util.Arrays.*;
import static java.util.stream.Collectors.*;

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


public class Main {

    static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());

        while (tc-->0){
             int[] input = stream(br.readLine().split(" "))
                      .mapToInt(Integer::parseInt).toArray();
             n = input[0];
             int m = input[1], w= input[2];

            graph = new ArrayList<>();
            IntStream.rangeClosed(0,n).forEach(e->graph.add(new ArrayList<>()));

            for(int i=0;i<m+w;i++){
                 input = stream(br.readLine().split(" "))
                          .mapToInt(Integer::parseInt).toArray();
                if(i<m){
                    graph.get(input[0]).add(new Node(input[1],input[2]));
                    graph.get(input[1]).add(new Node(input[0],input[2]));
                }else
                    graph.get(input[0]).add(new Node(input[1],-1*input[2]));
            }//end input

            if(bellmanford())
                System.out.println("YES");
            else
                System.out.println("NO");

        }

    }

    private static boolean bellmanford(){

        int[] distance = new int[n+1]; // distance 배열 0으로 초기화

        boolean update =false;

        for(int i=1; i<=n; i++){ // 수행횟수 : n-1(다익스트라) +1(최종확인) = n번
            update =false;
            for(int cur=1; cur<=n; cur++){  

                for (Node next : graph.get(cur)) {
                    if(distance[next.node] > distance[cur]+next.weight){
                        distance[next.node] = distance[cur]+next.weight;
                        update = true; 
                    }
                }
            }
            if(!update) // 음의 사이클이 없는 경우
                break;
        }
        return update;
    }

    static class Node{
        int node,weight;

        public Node(int node, int weight) {
            this.node = node;
            this.weight = weight;
        }
    }
}