[백준] 1865 - 웜홀

[문제링크]

1865번: 웜홀

 

0. 벨만-포드 알고리즘

 

1. 시작노드로부터, 모든 도로에 대해 n-1번 갱신하면 각 노드까지의 최소 거리

 

2. 한번 더 돌렸을때 변동되는 값이 존재한다면 음수 cycle이 존재하기 때문

 

3. 도달할 수 없는 노드도 갱신하도록 해 시작노드와 연결되지 않아도 음수 사이클은 탐지 가능

 

* 현재 코드는 a->b가 갱신됬을 때, 같은 단계에서 갱신된 b로 인해 b->c의 결과도 변할 수 있는 코드

  - 음수 사이클이 있다면 n번째 단계의 결과값은 이미 사이클을 몇번 돈 결과일 수 있다

  - 하지만 음수 사이클을 탐지할 땐 상관 없음

 

개선점 : 두 지점 사이에 여러 도로가 있을 수 있으므로, 입력단계에서 처리해 성능 향상 가능

 

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

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int tc = pint(br.readLine());
		for (int testcase = 1; testcase <= tc; testcase++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int n = pint(st.nextToken());
			int m = pint(st.nextToken());
			int w = pint(st.nextToken());
			ArrayList<ArrayList<int[]>>graph2=new ArrayList<>();
			for (int i = 0; i <= n; i++) {
				graph2.add(new ArrayList<>());
			}
			//도로 입력
			for (int i = 0; i < m; i++) {
				st = new StringTokenizer(br.readLine()," ");
				int n1 = pint(st.nextToken()), n2 = pint(st.nextToken());
				int cost = pint(st.nextToken());
				graph2.get(n1).add(new int[] {n2,cost});
				graph2.get(n2).add(new int[] {n1,cost});
			}
			//웜홀입력
			for (int i = 0; i < w; i++) {
				st = new StringTokenizer(br.readLine()," ");
				int n1 = pint(st.nextToken()), n2 = pint(st.nextToken());
				int cost = pint(st.nextToken())*-1;
				graph2.get(n1).add(new int[] {n2,cost});
			}
			int[] dist=new int[n+1];
			int[] dist2=new int[n+1];
			Arrays.fill(dist, 6000000);//이론상 최댓값 : 4990000
			dist[1]=0;//시작노드 1
			
			for (int i = 0; i < n-1; i++) {
				
				for (int j = 1; j <= n; j++) {
					for (int j2 = 0; j2 < graph2.get(j).size(); j2++) {
						int[] cur = graph2.get(j).get(j2);
						dist[cur[0]]=Math.min(dist[cur[0]], dist[j]+cur[1]);
					}
				}
				
			}//n-1번 실행
			
			//1번 더 실행
			dist2 = dist.clone();

			for (int j = 1; j <= n; j++) {
				for (int j2 = 0; j2 < graph2.get(j).size(); j2++) {
					int[] cur = graph2.get(j).get(j2);
					dist2[cur[0]]=Math.min(dist2[cur[0]], dist2[j]+cur[1]);
				}
			}
			//결과값이 달라진게 있다면 : 음수 cycle이 존재한다
			String ans = "NO";
			for (int i = 1; i <= n; i++) {
				if(dist[i]!=dist2[i]) {
					ans="YES";
					break;
				}
			}
			
			sb.append(ans).append("\n");
		}//end of tc
		System.out.println(sb);
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면