[JAVA] 백준 11657 : 타임머신

문제

11657번: 타임머신

해결 방법

 

벨만-포드 알고리즘을 사용해야 하는 문제이다.

한 정점에서 다른 모든 정점의 최단 경로를 탐색해야 하는데 Cost가 음인 경우 사용 가능하다.

 

최단 경로를 나타내는 배열을 최댓값으로 초기화 해준 다음 배열을 사용해서 탐색을 진행한다.

정점의 수 - 1 만큼 반복문을 통해 최단 경로를 탐색해주고, 

한 번 더 탐색하였을 때 또 최단 경로가 바뀐다고 하면 음의 사이클이 존재한다는 뜻이다.

 

여기서 말하는 음의 사이클이란 계속해서 최단 경로가 작아지는

즉, 1 -> 2 까지는 3만큼의 Cost로 이동할 수 있는데 2 -> 1로 올 때는 -4 만큼의 Cost로 이동이 가능하다.

이러한 경우 계속해서 최단경로가 줄어들게 되는데  이 같은 경우 음의 사이클이 존재한다고 말할 수 있다.

 

탐색이 모두 끝난 후 음의 사이클이 있다면 -1, 아니면 최단 경로를 출력하는데 최단 경로가 최댓값이면 그 정점은 탐색을 할 수 없었다는 뜻이므로 -1을 출력해준다.

 

코드

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

public class Main {
	static ArrayList<Node> list[];
	static long dp[];
	static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        
        list = new ArrayList[N + 1];
        dp = new long[N + 1];
        for (int i = 1; i <= N; i++) {
        	list[i] = new ArrayList<>();
        	dp[i] = Integer.MAX_VALUE;
        }
        
        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 cost = Integer.parseInt(st.nextToken());
        	
        	// 단방향으로 추가
        	list[start].add(new Node(end, cost));
        }
        
        
        StringBuilder sb = new StringBuilder();
        if(bellman()) {
        	for (int i = 2; i <= N; i++) {
        		if (dp[i] == Integer.MAX_VALUE) {
        			// 방문할 수 없었다는 뜻
        			sb.append(-1 + "\n");
        		} else {
        			sb.append(dp[i] + "\n");
        		}
        	}
        } else {
        	// 음의 사이클이 있는 경우
        	sb.append("-1");
        }
        System.out.println(sb);
    }
    
    static boolean bellman() {
    	dp[1] = 0;
    	
    	// 정점의 수 - 1 만큼 반복문을 돌림
    	for (int i = 1; i < N; i++) {
    		
    		// 1에서 출발해서 방문가능한 곳 탐색
    		for (int j = 1; j <= N; j++) {
    			for (Node node : list[j]) {
    				// 아직 해당 지점까지는 도착하지 못했으므로 탐색할 필요 없음.
    				if (dp[j] == Integer.MAX_VALUE) break;
    				
    				if (dp[node.next] > dp[j] + node.cost) {
    					dp[node.next] = dp[j] + node.cost;
    				}
    			}
    		}
    	}
    	
    	// 한번 더 탐색해서 또 값이 바뀌면 음의 사이클이 있다는 뜻
    	for (int i = 1; i <= N; i++) {
    		for (Node node : list[i]) {
    			if (dp[i] == Integer.MAX_VALUE) break;
				if (dp[node.next] > dp[i] + node.cost) return false;
			}
    	}
    	return true;
    }
}

class Node {
	int next;
	int cost;
	
	Node (int next, int cost) {
		this.next = next;
		this.cost = cost;
	}
}