백준 1719 - 택배

문제

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

리뷰

플로이드-워셜 알고리즘을 조금만 응용하면 풀 수 있는 문제였다.

우선 플로이드-워셜을 실현하기 위해 경로별 최단 비용을 저장하는 2차원
dist 배열과 경로 $i \rightarrow j$ 에서 $i$가 진입해야 할 첫 정점인 $k$ 를 저장하는
map 을 정의하였다.

이후, 간선 정보를 입력 받을 때 MAX_VALUE 로 초기값을 설정한 dist 뿐만
아니라 map 도 같이 갱신해주고, 플로이드-워셜 로직을 진행하며 최단 경로
비용 갱신시(dist[i][j] 갱신시) map[i][j]도 같이 갱신해주는 식으로
로직을 구성하였다.

유의할 점은 map[i][j]자체가 $i \rightarrow j$ 경로에서 진입하는 첫 정점의
번호이기 때문에 플로이드를 수행하며 map[i][j]를 갱신할 시에도 이를
map[i][k] 와 같은 형태로 활용해야 한다는 점이었다.

로직에서 가장 시간복잡도를 차지하는 플로이드-워셜 로직이 $O(N^3)$의 복잡도로
수렴하므로 최대 연산량은 $200^3$이다. 따라서 제한 조건인 2초를 무난히
통과한다.

코드

import java.util.*;

import static java.lang.Integer.parseInt;
import static java.lang.Integer.MAX_VALUE;

public class Main {
    static int N;
    static int[][] map;
    static int[][] dist;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        StringTokenizer st = new StringTokenizer(in.nextLine());
        N = parseInt(st.nextToken());
        int M = parseInt(st.nextToken());

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

        for (int i = 1; i < dist.length; i++) {
            for (int j = 1; j < dist[i].length; j++) {
                dist[i][j] = (i == j) ? 0 : MAX_VALUE;
            }
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(in.nextLine());
            int u = parseInt(st.nextToken());
            int v = parseInt(st.nextToken());
            int w = parseInt(st.nextToken());

            dist[u][v] = w;
            dist[v][u] = w;
            map[u][v] = v;
            map[v][u] = u;
        }


        floyd();

        for (int i = 1; i < map.length; i++) {
            for (int j = 1; j < map.length; j++)
                System.out.print(map[i][j] == 0 ? "- " : map[i][j] + " ");
            System.out.println();
        }
        in.close();
    }

    static void floyd() {
        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] == MAX_VALUE || dist[k][j] == MAX_VALUE)
                        continue;

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

결과