[백준/JAVA] 11404번: 플로이드

🔺 문제

11404번: 플로이드

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M;
    static int[][] distance; // 최단 거리 배열 - 인접 행렬
    static int max = 10000001;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine()); // 도시 개수
        M = Integer.parseInt(br.readLine()); // 버스 개수
        
        // 최단 거리 배열 초기화
        distance = new int[N + 1][N + 1];
        for(int i = 1 ; i <= N ; i++) {
            for(int j = 1 ; j <= N ; j++) {
                if(i == j) distance[i][j] = 0;
                else       distance[i][j] = max;
            }
        }
        
        // 인접 행렬 채우기
        for(int i = 1 ; i <= M ; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            int S = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());
            
            // 중복된 입력 받을 수 있으므로
            if(distance[S][E] > K) distance[S][E] = K; 
        }
        
        // 플로이드-워셜
        for(int K = 1 ; K <= N ; K++) {
            for(int i = 1 ; i <= N ; i++) {
                for(int j = 1 ; j <= N ; j++) {
                    if(distance[i][j] > distance[i][K] + distance[K][j])
                        distance[i][j] = distance[i][K] + distance[K][j];
                }
            }
        }
        
 
        for(int i = 1 ; i <= N ; i++) {
            for(int j = 1 ; j <= N ; j++) {
                if(distance[i][j] == max) System.out.print("0 ");
                else    System.out.print(distance[i][j] + " ");
            }
            System.out.println();
        }
    }
}

✅ 해결 아이디어
✔ 플로이드-워셜
- 3중 for문(K → S → E)

 

 

💥 유의사항

•  최단 경로 배열 초기화 할 때, i !=j인 경우 Integer.MAX_VALUE로 채우면 틀림

⇨ 100 * 100000보다 큰 수로 하면 됨. 

 

---

🔺 다른 풀이들

- 나랑 똑같은 에러 나셨던....ㅎ

[Java] 백준 11404번 [플로이드] 자바

 

---

💬 느낀 점

어렵진 않은데 저 방문하지 않은 노드일 때 무한대 값 넣을 때....

여기서 조금 이상하게 시간 소비했다..😥

 

 

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

 

 

(+6/26 2회독)

플로이드 워셜은.. DP였다..!!

import java.util.*;
import java.io.*;
 
public class Main {
    static int N,M;
    static int[][] dp;  // 최단 거리 배열
    static int INF = 987654321;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        N = Integer.parseInt(br.readLine());    // 도시 개수
        M = Integer.parseInt(br.readLine());    // 버스 개수
        
        // 최단 거리 배열 초기화
        dp = new int[N + 1][N + 1];
        for(int i = 1 ; i <= N ; i++) {
            for(int j = 1 ; j <= N ; j++) {
                dp[i][j] = (i == j) ? 0 : INF;
            }
        }
        
        // 입력 받아 그래프 데이터 채우기
        while(M --> 0) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            
            dp[s][e] = Math.min(dp[s][e], v);
        }
        
        // 플로이드-워셜 수행 (👊 K가 가장 바깥쪽!)
        for(int K = 1 ; K <= N ; K++) {
            for(int S = 1 ; S <= N ; S++) {
                for(int E = 1 ; E <= N ; E++) {
                    dp[S][E] = Math.min(dp[S][E], dp[S][K] + dp[K][E]);
                }
            }   
        }
        
        // 출력하기
        for(int i = 1 ; i <= N ; i++) {
            for(int j = 1 ; j <= N ; j++) {
                sb.append(dp[i][j] == INF ? 0 : dp[i][j]).append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
}
 

---

(참고)

✔ DO it 알고리즘 코딩테스트 자바편