백준 11657 - 타임머신

Java

11657 번 - 타임머신

문제

접근 방법

벨만 포드 알고리즘을 통해 해결하였다.

주의할 점은 각 노드의 비용을 담을 node의 자료형을 long으로 하여야한다.

코드

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

public class Main {
	static int n, m, result;
	static int INF = 999999999;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());
    	long[] node = new long[n + 1];
    	List<List<int[]>> graph = new ArrayList<>();
    	
    	for(int i = 0; i <= n; i++) {
    		node[i] = INF;
    		graph.add(new ArrayList<>());
    	}
    	node[1] = 0;
    	
    	int a,b,c;
    	
    	for(int i = 0; i < m; i++) {
    		stk = new StringTokenizer(br.readLine());
    		a = stoi(stk.nextToken());					
    		b = stoi(stk.nextToken());						
    		c = stoi(stk.nextToken());			
    		graph.get(a).add(new int[] {b,c});	
    	}
    	boolean isChanged = false;
    	// v - 1만큼 반복한다.
    	for(int i = 1; i <= n; i++) {
    		// 기준 노드를 하나 씩 정한다.
    		for(int j = 1; j <= n; j++) {
    			for(int[] edge : graph.get(j)) {
    				b = edge[0];
    				c = edge[1];
    				// 기준 노드가 무한대이면, 간선을 더하는 것이 의미가 없다.
    				// 기준 노드에서 다음 노드로 갔을 때 root에서 다음 노드로 간 것보다 싸면.
    				if(node[j] != INF && node[b] > node[j] + c)
    					node[b] = node[j] + c;
    			}
    		}
    		// 마지막, 음수 사이클이 존재하는지 확인
    		if(i == n) {
    			for(int j = 1; j <= n; j++) {
        			for(int[] edge : graph.get(j)) {
        				b = edge[0];
        				c = edge[1];
        				// 기준 노드가 무한대이면, 간선을 더하는 것이 의미가 없다.
        				// 기준 노드에서 다음 노드로 갔을 때 root에서 다음 노드로 간 것보다 싸면.
        				if(node[j] != INF && node[b] > node[j] + c)
        					isChanged = true;
        			}
        		}
    		}
    	}
    	
    	if(isChanged)
    		System.out.println(-1);
    	else {
	    	for(int i = 2; i <= n; i++) {
	    		if(node[i] == INF)
	    			System.out.println(-1);
	    		else
	    			System.out.println(node[i]);
	    	}
    	}
    	
    	br.close();
	}
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점