[백준] 11404 플로이드 - Graph Theory / Java

• 문제 링크

11404번: 플로이드

 

• 풀이 과정

모든 노드간 최단 경로를 구하는 Floyd-Warshall 알고리즘을 활용한다.

 

2차원 배열에 자기 자신 노드로 이동하는 경우을 제외한 모든 최단 거리를 inf 값으로 지정하고,

이때 inf 값을 Integer.MAX_VALUE 로 지정 시 오버플로우가 발생할 수 있으므로

정점과 간선의 최대값의 곱에 1을 더한 수로 지정하였다.

 

이 후 간선의 정보를 입력받는데 같은 간선이 추가로 주어질 시 가중치의 최소값을 매번 갱신하여,

dist 배열에 각각의 간선의 최소 가중치값이 저장된다. (dist[src][dest] = Math.min(dist[src][dest], weight))

 

floydWarshall 함수에서 3중 for문으로 출발점(i), 경유점(k), 도착점(j) 를 구현하고,

아래의 코드를 통해 특정 경로의 출발점에서 도착점까지의 거리와

출발점에서 경유점을 거쳐 도착점까지의 거리를 비교하여 최단 거리를 갱신한다.

if (dist[i][j] > dist[i][k] + dist[k][j])
	dist[i][j] = dist[i][k] + dist[k][j];

 

이렇게 모든 경로의 최단 거리가 저장된 dist 배열의 모든 원소를 정답으로써 출력하고,

만약 값의 변화가 없는 경로(dist[i][j] == inf) 는 존재하지 않는 경로이므로 0 을 출력한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

    static int n;
    static int[][] dist;
    static int inf = 10000001;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        dist = new int[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j)
                    continue;
                else
                    dist[i][j] = inf;
            }
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int src = Integer.parseInt(st.nextToken());
            int dest = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            dist[src][dest] = Math.min(dist[src][dest], weight);
        }

        floydWarshall();

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][j] == inf)
                    bw.write("0 ");
                else
                    bw.write(dist[i][j] + " ");
            }

            bw.write("\n");
        }

        bw.flush();
    }

    private static void floydWarshall() {
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                if (i == k)
                    continue;

                for (int j = 1; j <= n; j++) {
                    if (j == i || j == k)
                        continue;
                    if (dist[i][j] > dist[i][k] + dist[k][j])
                        dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

}