[BOJ/JAVA] 1719번: 택배

태그: Java

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

1719번: 택배

키워드

• 경로표는 한 집하장에서 다른 집하장으로 최단경로로 화물을 이동시키기 위해 가장 먼저 거쳐야 하는 집하장을 나타낸 것이다.

---

구현

바로 이동하는 것이 항상 최단경로를 의미하는 것은 아니다.

따라서 최단 경로를 찾아줘야 한다.

• 모든 한 노드에서 다른 노드까지의 최단경로를 구하기 위해서 floydWarshall 알고리즘을 사용했다.
• floydWarshall 알고리즘에서 [i]를 경유한다고 했을 때 [j] → [k]로 바로 가는 방법과 [j]→[i]→[k]로 경유하여 가는 방법 중 [i]를 경유하는 방법이 더 짧을 때 [i]위치를 중간 지점으로 저장한다.
• 중요한 것은 중간 지점으로 저장한 곳이 바로 다음에 들리는 경로는 아니다. 바로 다음 지점에 들리는 경로를 찾기 위해서 재귀함수를 이용했다.이를 이 때 end값을 boardRoute[start][end] 값으로 갱신하여 이 값이 -1이 될 때 end값을 최초 경유지로 다시 저장한다.
• findRoute 메소드를 이용하여 (start,end) 사이 boardRoute[start][end] 의 값이 -1이 아니라면 start→end 사이에 들리는 경유지가 있다는 뜻이다.

---

코드

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

public class java_1719 {
    // 집하장의 갯수
    static int n;
    // 경로의 갯수
    static int m;

    static int board[][];
    static int boardRoute[][];

    static void floydWarshall() {
        boardRoute = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                boardRoute[i][j] = j;
            }
            boardRoute[i][i] = -1;
        }

        // i를 들려서
        // j에서
        // k로 가는 방법
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    // 경유가 가능하다면
                    if (board[j][i] != Integer.MAX_VALUE && board[i][k] != Integer.MAX_VALUE) {
                        // 비용이 더 작다면
                        if (board[j][i] + board[i][k] < board[j][k]) {
                            // j-k를 가기위해 i를 들려야 한다.
                            boardRoute[j][k] = i;
                            board[j][k] = board[j][i] + board[i][k];
                        }
                    }
                }
            }
        }
    }

    // start에서 end로 갈 때 바로 들려야 하는 곳
    static int findRoute(int start, int end) {
        if (boardRoute[start][end] == end) {
            return end;
        }
        return findRoute(start, boardRoute[start][end]);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        board = new int[n][n];

        for (int i = 0; i < n; i++) {
            Arrays.fill(board[i], Integer.MAX_VALUE);
            board[i][i] = 0;
        }

        // 비용 저장
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());

            int from = Integer.parseInt(st.nextToken()) - 1;
            int to = Integer.parseInt(st.nextToken()) - 1;

            int cost = Integer.parseInt(st.nextToken());

            board[from][to] = cost;
            board[to][from] = cost;
        }

        floydWarshall();

        // 최단경로를 위한 경로표의 작성
        for (int i = 0; i < n; i++) {
            // i에서 j로 가는 데 가장 먼저 들리는 곳 저장
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    boardRoute[i][j] = findRoute(i, j);
                }

            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (boardRoute[i][j] == -1) {
                    System.out.print("- ");
                } else {
                    System.out.print((boardRoute[i][j] + 1) + " ");
                }

            }
            System.out.println();
        }
        // A -> B 로 가기 위한 최단 경로 사이에
        // C가 존재한다.
        // A -> C -> B 순서로 간다.

        // dist 줄어드는 연산을 할 때 삽입할것?

        // 다익스트라보다 floydWarshall 쓰는게 맞을지도

        br.close();
    }
}

---