백준 11404번 - 플로이드 (JAVA)

문제링크

 

 

문제 풀이 과정

플로이드-워셜 알고리즘을 학습 할 수 있는 기본적인 문제라고 생각한다. 플로이드-워셜 알고리즘을 그대로 사용하여 문제를 해결하였다.

다만 제출 할때 항상 98% 에서 틀렸습니다가 나와서 의문이였다.

알고보니 MAX 값으로 잡았던 값이 작아서 문제가 되었다. 여기서 MAX 값을 Integer.MAX_VALUE 로 잡으면 오버플로워가 발생하게 된다.

 

전체 코드

 

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.StringTokenizer;
	public class Main {
	static int[][] distance;
	static int city, bus;
	static final int MAX = 10000001;
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static void main(String[] args) throws IOException {
	city = Integer.parseInt(br.readLine());
	bus = Integer.parseInt(br.readLine());
	distance = new int[city + 1][city + 1];
	for (int i = 1; i <= city; i++) {
	for (int j = 1; j <= city; j++) {
	if(i == j){
	distance[i][j] = 0;
	}
	else{
	distance[i][j] = MAX;
	}
	}
	}
	input();
	floyd();
	print();
	}
	public static void input() throws IOException {
	for (int i = 0; i < bus; i++) {
	StringTokenizer st = new StringTokenizer(br.readLine());
	int a = Integer.parseInt(st.nextToken());
	int b = Integer.parseInt(st.nextToken());
	int c = Integer.parseInt(st.nextToken());
	if(distance[a][b] > c) distance[a][b] = c;
	}
	}
	public static void floyd(){
	for (int k = 1; k <= city; k++) {
	for (int i = 1; i <= city; i++) {
	for (int j = 1; j <= city; j++) {
	if(distance[i][j] > distance[i][k] + distance[k][j]){
	distance[i][j] = distance[i][k] + distance[k][j];
	}
	}
	}
	}
	}
	public static void print(){
	for (int i = 1; i <= city; i++) {
	for (int j = 1; j <= city; j++) {
	if(distance[i][j] == MAX){
	System.out.print(0 + " ");
	}
	else{
	System.out.print(distance[i][j] + " ");
	}
	}
	System.out.println();
	}
	}
	}

view raw floyd.java hosted with ❤ by GitHub