[백준 알고리즘] 1865번: 웜홀 (Java / 자바)

음수사이클이 있는지 판단하는 문제이다.

어려운 점은 특정 지점에서 시작했을 때 사이클이 존재하는지 판단하는게 아니라

전체 그래프에서 음수사이클이 발생하는경우가 있는지 체크해야한다.

1) 모든 지점에서 벨만포드 수행

- 이렇게도 풀 수 있다고 한다.

2) 가상 시작점 만들기

- 나는 이렇게 풀었는데,

안쓰는 0번에서 단방향으로 모든 vertex에 가중치 0으로 연결해줬다.

그리고 나서 벨만포드의 시작점을 0번으로 해서

0->1,2,3,4.... ->0 (사이클발생) -> 1,2,3,4... (갱신 과정에서 사이클 탐지)

이런 방식으로 벨만포드를 한번만 수행하고 풀 수 있었다.

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

// 특정 지점에서 출발해서 다시 돌아와야함
// 모든 지점에서 dfs 수행? 불가
// 벨만 포드 사용 O(VE) -> O(500*(2700)) -> O(1250000) 한번 수행에 백만정도
// * T(5) 
// 음수 사이클 판별로 풀기

public class boj1865 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int T, N, M, W;
	static final int INF = 1000000000;
	static int[] dist; // 출발지부터의 거리를 기록하는 배열
	static ArrayList<Edge> edges;
	
	static class Edge {
		int v; // 나가는 정점
		int w; // 들어오는 정점
		int cost;
		
		public Edge(int v, int w, int cost) {
			this.v = v;
			this.w=w;
			this.cost=cost;
		}
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		T = Integer.parseInt(br.readLine());
		for (int t=0; t<T; t++) {
			input();
			boolean isCycle = bellmanFord();
			if (isCycle) System.out.println("YES");
			else System.out.println("NO");
		}
	}
	
	static private boolean bellmanFord() {
		dist = new int[N+1];
		Arrays.fill(dist, INF);
		
		dist[0] = 0; // 시작점
		
		for (int i=0; i<=N; i++) {  // 정점 개수만큼 반복
			for (int j=0; j<edges.size(); j++) {  // 간선 개수만큼 반복
				Edge edge = edges.get(j);  // 현재 간선
				
				// 현재 간선에서, 들어오는 정점에 대해 비교
				if (dist[edge.v] != INF && dist[edge.w] > dist[edge.v] + edge.cost) {
					// 갱신 조건: 새롭게 들어오는 정점 v + cost 가 더 효율적 (기존 dist에 저장된 도착점보다)
					dist[edge.w] = dist[edge.v] + edge.cost;
				}
			}
		}
		
		// 음수 사이클 탐지 (위에서 한번 다 돌렸는데 또 갱신되는경우)
		for (int i=0; i<edges.size(); i++) {
			Edge edge = edges.get(i);
			if (dist[edge.v] != INF && dist[edge.w] > dist[edge.v] + edge.cost) {
				return true; // 음수 사이클 있음
			}
		}
		
		return false;
	}
	
	static private void input() throws IOException {
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		W = Integer.parseInt(st.nextToken());
		
		edges = new ArrayList<>();
		
		for (int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int v = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			edges.add(new Edge(v, w, c));
			edges.add(new Edge(w, v, c));
		}
		for (int i=0; i<W; i++) {
			st = new StringTokenizer(br.readLine());
			int v = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			edges.add(new Edge(v, w, -c));
		}
		
		// 가장 시작점에서 모든 지점 연결
		for (int i=1; i<=N; i++) {
			edges.add(new Edge(0, i, 0));
		}
	}
}