[JAVA] BOJ 백준 11404번 - 플로이드

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

---

2. 내가 푼 방법

플루이드 와샬 알고리즘을 사용해 문제를 풀었다.

 

주의해야 할 두 가지만 설명하자면, 첫 번째로 입력 값으로 동일한 경로(출발지, 도착지)에 다른 비용을 가지는 값이 있을 수도 있다는 점과 두 번째로 단방향 연결이므로 플루이드 와샬 알고리즘을 작성할 때 0 값을 처리해주어야 한다는 점을 조심해야한다.

 

if 문을 통해 더 작은 비용을 가지는 값을 저장하도록 해주었다.

int N = Integer.parseInt(br.readLine());
int M = Integer.parseInt(br.readLine());
arr = new int[N+1][N+1];

for (int m = 0; m < M; m++) {
    StringTokenizer st = new StringTokenizer(br.readLine());

    int a = Integer.parseInt(st.nextToken());
    int b = Integer.parseInt(st.nextToken());
    int w = Integer.parseInt(st.nextToken());

    if (arr[a][b] == 0) arr[a][b] = w;
    else if (arr[a][b] > w) arr[a][b] = w;
}

 

또한 플루이드 와샬 알고리즘에서 arr[i][k] == 0 혹은 arr[k][j] == 0 일 경우에는 continue문으로 건너뛰어주었다.

for (int k = 1; k <= N; k++) {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (i == j) continue;
            if (arr[i][k] == 0 || arr[k][j] == 0) continue;

            if (arr[i][j] == 0 || arr[i][j] > arr[i][k] + arr[k][j]) {
                arr[i][j] = arr[i][k] + arr[k][j];
            }
        }
    }
}

---

3. 자바 코드

깃허브 풀이 주소

https://github.com/geujeog/BOJ/blob/main/B11404.java

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

class Main {
    static int N;
    static int[][] arr;

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

        N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        arr = new int[N+1][N+1];

        for (int m = 0; m < M; m++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            if (arr[a][b] == 0) arr[a][b] = w;
            else if (arr[a][b] > w) arr[a][b] = w;
        }

        minCost();

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                bw.write(arr[i][j]+" ");
            }
            bw.write("\n");
        }

        br.close();
        bw.flush();
        bw.close();
    }

    public static void minCost () {

        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (i == j) continue;
                    if (arr[i][k] == 0 || arr[k][j] == 0) continue;

                    if (arr[i][j] == 0 || arr[i][j] > arr[i][k] + arr[k][j]) {
                        arr[i][j] = arr[i][k] + arr[k][j];
                    }
                }
            }
        }

    }
}

---

4. 결과 및 회고

플로이드 와샬 알고리즘 코드를 짤 때 단방향 연결 처리를 해줘야 한다는 것을 뒤늦게 깨달았다.

그래도 삽질한 만큼 기억에 잊혀지지 않을 것 같다. ㅎㅎ