[백준] 11657 타임머신 #JAVA 출력초과

BAEKJOON [11657] 타임머신 

---

코드

---

 

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

class Node{
	int start;
	int end;
	int dist;
	
	public Node(int start, int end, int dist) {
		this.start = start;
		this.end = end;
		this.dist = dist;
	}
}

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new  BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st ;
		
		st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken()); //노드의 갯수  
		int m = Integer.parseInt(st.nextToken()); //간선의 갯수 
		
		List<Node> list = 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 dist = Integer.parseInt(st.nextToken());
	
			list.add(new Node(start, end, dist));
		}
		
		bellmanFord(n, list);

	}
	
	static void bellmanFord(int n, List<Node> list) {
		
		boolean flag = false;
		
		long[] distance = new long[n+1]; //int 자료형은 출력 초과
		Arrays.fill(distance, Integer.MAX_VALUE);
		
        distance[1] = 0; //출발 1에서 시작, 자기자신 초기화
		
		for (int i = 0; i < n; i++) {
			
			//모든 간선 확인
			for (int j = 0; j < list.size(); j++) {
				int s = list.get(j).start;
				int e = list.get(j).end;
				int d = list.get(j).dist;
				
				if(distance[s] != Integer.MAX_VALUE && distance[e] > distance[s] + d) {
					distance[e] = distance[s] + d;
					
					if(i == n-1) flag = true; // 마지막 반복에서도 값이 갱신된다면 음의 순환 존재 
				}
				
			}
		}
		
		if(flag) {
			System.out.println("-1");
		}else {
			StringBuilder sb = new StringBuilder();
			
			for (int i = 2; i <= n; i++) {
				if(distance[i] == Integer.MAX_VALUE) {
					sb.append("-1\n");
				}else {
					sb.append(distance[i]+"\n");
				}
			}
			
			System.out.println(sb.toString());
		}
		
	}

}

 

 

 

 

풀이

---

• 벨만포드
• 출력초과로 당황했던 문제
• N = 500, M = 6000 인 경우 최대 300만번의 반복문을 돌게 된다. 이때 음의 간선이 -10,000 이라면 약 -300억의 값으로 underflow가 발생하게 되어 출력초과가 나오는 경우가 발생한다. 때문에 거리배열의 자료형을 long으로 선언해야 했다.

 

 

---

잘못된 코드나 내용이 있다면 댓글을 남겨주세요. 즉시 수정하도록 하겠습니다! :)

 

 

글올리기전에 태그 작성하고,,, <hr> 제대로 나오는지 미리보기로 확인하고 올리자!!!!