[코드트리/NOVICE HIGH] 중앙교통통제소 (JAVA)

🔺 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int INF = 987654321; // Integer.MAX_VALUE로 하면 틀림
 
    static int[][] dist;
    
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
        
        // 최단 거리 배열 초기화
        dist = new int[7][7];
        for(int i = 1 ; i <= 6 ; i++) {
            for(int j = 1 ; j <= 6 ; j++)
                dist[i][j] = (i == j) ? 0 : INF;
        }
        
        // 양방향
        dist[1][2] = 2; dist[2][1] = 2;
        dist[1][3] = 5; dist[3][1] = 5;
        dist[1][4] = 1; dist[4][1] = 1;
        
        dist[2][3] = 3; dist[3][2] = 3;
        dist[2][4] = 2; dist[4][2] = 2;
        
        dist[3][4] = 3; dist[4][3] = 3;
        dist[3][5] = 1; dist[5][3] = 1;
        dist[3][6] = 5; dist[6][3] = 5;
        
        dist[4][5] = 1; dist[5][4] = 1;
        
        dist[5][6] = 2; dist[6][5] = 2;
        
 
        // 🔔 플로이드 와샬
        for(int k = 1 ; k <= 6 ; k++) {
            for(int i = 1 ; i <= 6 ; i++) {
                for(int j = 1 ; j <= 6; j++) {
                    if(dist[i][j] > dist[i][k] + dist[k][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
        
        // 출력하기
        for(int i = 1 ; i <= 6 ; i++) {
            for(int j = 1 ; j <= 6 ; j++)
                sb.append(dist[i][j] == INF ? "INF" : dist[i][j]).append(" ");
            sb.append("\n");
        }
        System.out.println(sb);
    }
}

💥 유의사항

• INF를 초기화할 때, Integer.MAX_VALUE로 하면 틀림

⇨ 오버플로우 발생 가능하므로

     플로이드 와샬에서는 INF 값 초기화 시,

     Integer.MAX_VALUE 대신 충분히 큰 값 사용

 

---

💬 느낀 점

이렇게만 풀면 얼매나 좋게요....

입력값 양방향으로 하나하나 넣는 게 조굼 귀찮았다,,

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

플로이드-워셜