[백준 알고리즘] 11404번: 플로이드 (Java / 자바)

플로이드 워셜 알고리즘을 연습하기 좋은 문제였다.

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

public class boj_11404 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int N, M;
    static int[][] dist;
    public static void main(String[] args) throws IOException {
        input();
        floydWarshall();
        print();
    }

    static private void floydWarshall() {
        for (int k=1; k<=N; k++) {  // 경유
            for (int i=1; i<=N; i++) {  // 출발
                for (int j=1; j<=N; j++) {  // 도착
                    // i에서 j로 가려고 할 때, 직접 가는 것보다 k를 "경유"해서 가는 게 더 빠른가?
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);  // 빠른 경우 갱신
                }
            }
        }
    }

    static private void print() {
        for (int i=1; i<=N; i++) {
            for (int j=1; j<=N; j++) {
                if (dist[i][j] == 10000000) dist[i][j] = 0;
                System.out.print(dist[i][j] + " ");
            }
            System.out.println();
        }
    }

    static private void input() throws IOException {
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        dist = new int[N+1][N+1];

        for (int i=1; i<=N; i++) {
            Arrays.fill(dist[i], 10000000);
            dist[i][i] = 0; // 자기 자신으로 가는 경로 0 처리
        }

        for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            dist[a][b] = Math.min(dist[a][b], c);
        }
    }
}

    static private void input() throws IOException {
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        dist = new int[N+1][N+1];

        for (int i=1; i<=N; i++) {
            Arrays.fill(dist[i], 10000000);
            dist[i][i] = 0; // 자기 자신으로 가는 경로 0 처리
        }

        for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            dist[a][b] = Math.min(dist[a][b], c);
        }
    }
}

 

3번 틀렸는데,

첫번째는 INF를 무한대로 해서 틀렸다 . 가중치가 누적되므로 무한대로 하면 안된다...

두번째는 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다라는 조건을 체크하지 못해서 틀렸다.
입력받을 때 최솟값 갱신을 하도록 변경해준다.

   for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            dist[a][b] = Math.min(dist[a][b], c); // here
   }

 

세번째는 출력 시에 아예 가지 못하는 곳을 INF 로 그대로 출력해서 틀렸다.
만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다라는 조건이 있었다.

 

조건을 잘 확인하자~