백준 11404 - 플로이드

Java

11404 번 - 플로이드

문제

접근 방법

플로이드 - 와샬로 해결 할 수 있는 문제였다.

쉽게 접근을 하였지만, 98%에서 계속 틀렸는데, 이는 MAX_VALUE를 99999로 작게 두어서 발생하였다.
최대 거리가 100000 이므로, 100 * 100000 이상의 값을 두어야 문제 없이 해결 가능하다.

코드

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

public class Main {
	static int n, m, result;
	static int MAX_VALUE = 999999999;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	n = stoi(br.readLine());
    	StringTokenizer stk;
    	m = stoi(br.readLine());
    	
    	int[][] graph = new int[n + 1][n + 1];
    	
    	
    	for(int i = 1; i <= n; i++) {
    		Arrays.fill(graph[i], MAX_VALUE);
    		graph[i][i] = 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());
    		
    		if(graph[a][b] == 0 || graph[a][b] > c) {
    			graph[a][b] = c;
    		}
    	}
    	
    	// 플로이드 와샬 사용
    	for(int i = 1; i <= n; i++) {
    		for(int j = 1; j <= n; j++) {
    			if(i == j)
    				continue;
    			for(int k = 1; k <= n; k++) {
    				if(graph[j][k] > graph[j][i] + graph[i][k])
    					graph[j][k] = graph[j][i] + graph[i][k];
    			}
    		}
    	}
    	StringBuilder sb = new StringBuilder();
    	for(int i = 1; i <= n; i++) {
    		for(int j = 1; j <= n; j++) {
    			if(graph[i][j] == MAX_VALUE)
    				sb.append(0).append(" ");
    			else
    				sb.append(graph[i][j]).append(" ");
    		}
    		sb.append("\n");
    	}
    	
    	System.out.println(sb.toString());
    	br.close();
	}
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점