21.09.02 [백준] 11404 플로이드

[blossun]

• 문제

아이디어

• 경로(edge)가 나왔는지 안나왔는지를 INF로 확인 - int INF = 100_000_001; 최댓값 + 1 → 가독성 좋음
  • INF값을 설정할 때는 INF + INF 값이 데이터 타입의 표현값을 넘어가는지 확인이 필요하다. (주의)
• 또는, 그냥 0으로 초기화된 상태에서 최단거리 갱신할 때, 0인지 아닌지 체크하는 코드 추가. 자기자신으로 가는 경로인 경우 skip

어려운점 & 실수

정답

• StringTokenizer, StringBuilder로 최적화

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

public class N11404 {
 public static void main(String[] args) throws IOException {
 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 StringTokenizer token;
 int vertex = Integer.parseInt(br.readLine());
 int Edge = Integer.parseInt(br.readLine());
 int[][] arr = new int[vertex][vertex];
 int INF = 100_000_001; //최댓값 +1
 // 모든 경우의 수를 INF로 초기화하고 자기자신으로 가는 경로는 0으로 갱신
 for (int i = 0; i < vertex; i++) {
 Arrays.fill(arr[i], INF);
 arr[i][i] = 0;
 }

 // 간선 1개로 건널 수 있는 곳 초기화 "중간에 다른 정점을 거치지 않았을 때 최단 거리"
 for (int i = 0; i < Edge; i++) {
 token = new StringTokenizer(br.readLine());
 int from = Integer.parseInt(token.nextToken()) - 1;
 int to = Integer.parseInt(token.nextToken()) - 1;
 int cost = Integer.parseInt(token.nextToken()) - 1;
 arr[from][to] = Math.min(arr[from][to], cost);
 }

 //floyd 알고리즘
 for (int mid = 0; mid < vertex; mid++) { // (a -> b)경로를 1 ~ V 노드를 거쳐서 갈 때의 최단 거리 갱신
 for (int start = 0; start < vertex; start++) { // (start -> mid)
 for (int end = 0; end < vertex; end++) { // (mid -> end)
 int newCost = arr[start][mid] + arr[mid][end];
 arr[start][end] = Math.min(arr[start][end], newCost);
 }
 }
 }

 StringBuilder sb = new StringBuilder();
 for (int[] ints : arr) {
 Arrays.stream(ints).forEach(n -> {
 if (n == INF) n = 0;
 sb.append(n).append(" ");
 });
 sb.append("\n");
 }
 System.out.println(sb);
 }
}