#백준_1865 웜홀 - Java 자바

#유형 : SPP, 벨만 포드

#난이도 : 골드 4

#  음수 사이클이 존재하는지 체크하는 문제이다. 있으면 YES 출력, 아니면 No 출력이다.  => 문제 조건에 비용이 음수인 경로가 존재한다(웜홀) 따라서 벨만포드 알고리즘(음의 사이클 체크 가능)으로 접근하면 된다. 아래의 벨만포드 알고리즘 특성 1번인 V-1개의 간선만 사용할 수 있다를 활용한다면, V-1번의 반복문을 돌고난 후에도 최단경로가 발생된다면(cnt >= N) 음의 가중치, 즉 웜홀을 통해 시간이 되돌아가는 경우 => 문제에서 요구하는 바이다. 또한 2번 특성도 활용하여 업데이트가 되는 노드가 없으면 반복문을 종료한다.

 

** 벨만포드 알고리즘 특성 **

1.최단 경로는 사이클을 포함할 수 없다. 따라서 최대 |V|-1개의 간선만 사용할 수 있다. 
2.최단 거리가 업데이트 되는 노드가 없어질 때 까지 계속해서 반복하여 구해준다. 이때 만약 음의 값을 가지고 있는 간선으로 인해 업데이트를 무한히 하게 되는 경우 탈출 시켜주어야 한다.(무한히 반복할 때는 최단거리가 없다고 한다.) 

 

** 최단 경로를 구하는 SPP 알고리즘인 다익스트라에서는 그리디 기법을 기반으로 하기 때문에 추후에 가중치가 감소하는 음수 가중치에 대해서는 처리를 못하였다.

** 하지만 벨만포드 알고리즘은 그것을 보완한 방식으로써 음의 가중치를 계산할 수 있다. 그러나 모든 정점에서 간선을 다 보아야 하기 때문에 시간 복잡도가 높다.

 

package bj;
 
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class p1865 {
    static int tc, N, M, W;
    static ArrayList<Point>[] arrList;
    static int dist[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        tc = Integer.parseInt(br.readLine());
        for(int t=1; t<=tc; t++) {
            
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());
            
            arrList = new ArrayList[N+1];
            dist = new int[N+1];
            
            for(int i=0; i<=N; i++)
                dist[i] = 987654321;
            
            for(int i=0; i<=N; i++)
                arrList[i] = new ArrayList<>();
            
            //도로의 정보
            for(int i=0; i<M; i++) {
                st = new StringTokenizer(br.readLine());
                int start = Integer.parseInt(st.nextToken());
                int end = Integer.parseInt(st.nextToken());
                int time = Integer.parseInt(st.nextToken());
                arrList[start].add(new Point(end, time));
                arrList[end].add(new Point(start, time));
            }
            //웜홀의 정보
            for(int i=0; i<W; i++) {
                st = new StringTokenizer(br.readLine());
                int start = Integer.parseInt(st.nextToken());
                int end = Integer.parseInt(st.nextToken());
                int time = Integer.parseInt(st.nextToken());
                arrList[start].add(new Point(end, -time));
            }
            
            boolean isPossible = true;
            dist[1] = 0;
            int cnt = 0;
            
            // cnt 가 N과 같거나 N보다 크다면 음의 사이클이 존재하는 것이다 && 더이상 업데이트가 없으면 종료한다.
            while(isPossible && cnt < N) {
                isPossible = false;
                cnt++;
                for(int v=1; v<=N; v++) {
                    for(Point po : arrList[v]) {
                        if(dist[v] + po.y < dist[po.x]) {
                            dist[po.x] = dist[v] + po.y;
                            isPossible = true;
                        }
                    }
                }
            }
            if(cnt == N)
                System.out.println("YES");
            else
                System.out.println("NO");
            
        }
        
    }
}