[백준] 11404 플로이드 (Java) [FloydWashal]

문제

https://www.acmicpc.net/problem/11404

11404번: 플로이드

 

알고리즘

플로이드 와샬

 

풀이

전형적인 플로이드 와샬 알고리즘이다.

"시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다." 조건이 있기 때문에,

input 값 입력시 dist[from][to] = Math.min(dist[from][to], w); 처리를 해준다.

이것만 주의하면 되며, 플로이드 와샬을 통해 문제를 풀면 된다.

 

코드

package com.company;

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

public class Test_FloydWashal {
    static int[][] dist;
    static int N, M;
    static final int INF = 987654321;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(bf.readLine());
        M = Integer.parseInt(bf.readLine());

        dist = new int[N + 1][N + 1];

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                dist[i][j] = INF;

                if (i == j)
                    dist[i][j] = 0;
            }
        }

        for (int i = 0; i < M; i++) {
            int from, to, w;
            StringTokenizer st = new StringTokenizer(bf.readLine());
            from = Integer.parseInt(st.nextToken());
            to = Integer.parseInt(st.nextToken());
            w = Integer.parseInt(st.nextToken());

            // 출발 도시와 도착 도시가 같지만 시간이 다른 입력값이 들어올 수 있음.
            // 예를 들어 "1 4 1"과 "1 4 2"가 입력으로 들어왔으면,
            // "1 4 1"을 택해야 함.
            dist[from][to] = Math.min(dist[from][to], w);
        }

        floydWashal();

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (dist[i][j] == INF) {
                    dist[i][j] = 0;
                }

                sb.append(dist[i][j] + " ");

            }
            sb.append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    public static void floydWashal() {
        //거처가는 노드
        for (int k = 1; k <= N; k++) {
            //출발점
            for (int i = 1; i <= N; i++) {
                //도착점
                for (int j = 1; j <= N; j++) {
                    if (dist[i][k] + dist[k][j] < dist[i][j])
                        dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}