(JAVA) [BOJ]백준 11404번, 플로이드

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

11404번: 플로이드

 

 

11404, 플로이드

📌 난이도 : Gold 4

📌 알고리즘 : 플로이드 와샬 (Floyd-Warshall)

 

이번 문제는 문제 이름에서부터 알 수 있듯이 플로이드 와샬 문제이다.

a -> b 도시에 가는데 비용이 주어지는데 중복이 있을 수 있으므로 최소 값을 저장해야 한다.

 

📚 Process

초기화 및 선언

: 도시의 개수 N, 버스의 개수 M을 입력받고 M개만큼의 비용이 주어진다. 이것을 단방향으로 연결해 주어야 한다.

그 전에 여기서 i와 j가 같은 경우는 자신 노드이므로 0으로 초기화 해주고 그 외에는 INF로 큰 값을 부여한다.  (최단 거리 계산을 위해)

public static void input() throws IOException{
    N = Integer.parseInt(br.readLine()); // 도시
    M = Integer.parseInt(br.readLine()); // 버스
    arr = new int[N+1][N+1];

    // 자신 노드에서 자신 노드를 제외한 모든 정점의 값을 INF로 초기값 설정
    // INF의 의미는 해당 노드에서 특정 노드까지 가는 길이 없다는 뜻!
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            arr[i][j] = INF;
            if (i == j)  arr[i][j] = 0;
        }
    }

    StringTokenizer st;
    int a,b,c;
    while(M-- > 0) {
        st = new StringTokenizer(br.readLine(), " ");
        a = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        // 최소 비용을 저장
        arr[a][b] = Math.min(arr[a][b], c);
    }
}

플로이드 와샬

: 모든 구역을 탐색하며 한번에 가는 것보다 거쳐서 가는 비용이 더 적을 경우, 최단 경로로 초기화해준다.

public static void pro() {
    for(int i=1;i<=N; i++) {
        for(int j=1;j<=N; j++) {
            for(int k=1;k<=N; k++) {
                // 한번에 가는 것보다 거쳐서 가는 비용이 더 적을 경우, 최단경로로 설정
                if(arr[j][k] > arr[j][i] + arr[i][k]) {
                    arr[j][k] = arr[j][i] + arr[i][k];
                }
            }            
        }            
    }
}

 

✅ 전체 코드

: 실제로 다익스트라와 플로이드 와샬의 문제가 많이 출제되는 것 같아 익숙해지면 좋을 것 같다.

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, M;
    static int[][] arr;
    static int INF = 987654321;
    public static void main(String[] args) throws IOException{
        input();
        pro();
        output();
    }

    public static void input() throws IOException{
        N = Integer.parseInt(br.readLine()); // 도시
        M = Integer.parseInt(br.readLine()); // 버스
        arr = new int[N+1][N+1];

        // 자신 노드에서 자신 노드를 제외한 모든 정점의 값을 INF로 초기값 설정
        // INF의 의미는 해당 노드에서 특정 노드까지 가는 길이 없다는 뜻!
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                arr[i][j] = INF;
                if (i == j)  arr[i][j] = 0;
            }
        }

        StringTokenizer st;
        int a,b,c;
        while(M-- > 0) {
            st = new StringTokenizer(br.readLine(), " ");
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
            // 최소 비용을 저장
            arr[a][b] = Math.min(arr[a][b], c);
        }
    }

    public static void pro() {
        for(int i=1;i<=N; i++) {
            for(int j=1;j<=N; j++) {
                for(int k=1;k<=N; k++) {
                    // 한번에 가는 것보다 거쳐서 가는 비용이 더 적을 경우, 최단경로로 설정
                    if(arr[j][k] > arr[j][i] + arr[i][k]) {
                        arr[j][k] = arr[j][i] + arr[i][k];
                    }
                }            
            }            
        }
    }
    public static void output() throws IOException{
        StringBuilder sb = new StringBuilder();
        for(int i=1;i<=N; i++) {
            for(int j=1;j<=N; j++) {
                // 가는 길이 없다면 초기화
                if (arr[i][j] == INF) {
                    arr[i][j] = 0;
                }
                sb.append(arr[i][j]+" ");
            }            
            sb.append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}