BOJ 1719 : 택배

풀이 요약

최단 경로 알고리즘 (다익스트라, 플로이드 워셜)

풀이 상세

다익스트라

1. 인접리스트를 통해, 입력에 대한 Edge 를 받는다.

2. 현재 좌표까지의 거리값을 저장할 dist[][] 와 대표값을 나타내는 p[][] 을 생성하여, dist[][] 는 MAX 값으로, p[][] 는 열의 인덱스로 초기화한다.

3. 시작 좌표 거리를 0 으로 하여 다익스트라를 통해 다음 갈 좌표를 탐색한다. 최단 경로가 업데이트 되는 경우, dist[][] 값을 새롭게 저장하고, p[][] 이전 지나온 좌표를 저장한다.

4. 해당 문제의 정답은 각 출발하는 곳에서 해당 좌표에 도착하기까지 지나온 좌표 가운데 가장 처음 지나는 노드를 각 인덱스마다 출력하는 것이다. 따라서 p[][] 를 기반으로 맨 처음 출발지점이 나올 때 까지 재귀함수를 호출하여, 이전 경로를 탐색하면 출력해야하는 값을 찾을 수 있다.

플로이드 워셜

1. 인접 행렬을 통해, 각 간선 간의 거리 값을 미리 받는다.

2. 이번에는 인접행렬의 값을 MAX 로, p[][] 은 그대로 열의 인덱스로 초기화한다. 단 인접행렬의 경우, 인접리스트와는 노드가 매칭 순서가 다르게 진행이 되므로, MAX 의 값을 너무 크게 잡으면 안된다. Integer.MAX_VALUE + k 값이 음수가 나와서 최단 경로로 될 수도 있기 때문이다.

3. 플로이드 워셜에서도 동일하게, p[][] 에 이전의 값을 저장하며 최단 경로를 업데이트 해야한다. 임의의 값 k 를 지나는 경우 더 짧은 경우 업데이트가 되는 것이기 때문에 p[출발점][도착점] 의 출발 이후 처음 지나는 경로는 p[출발점][k] 가 된다.

4. p[][] 가 이미 출발지점이 도착지점까지 가는데 처음 지나는 좌표를 저장하고 있으므로, 탐색 없이 바로 출력하면 된다.

배운점

• 인접 행렬을 오랜만에 써봤는데, 인접리스트와 탐색 순서가 전혀 다르다. 인접 행렬을 사용한 초기화를 인접 리스트에 그대로 적용시키는 경우 출력이 잘못될 수 있으니 주의 하자.

다익스트라

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer stk;
    static int N,M,dist[][],p[][];
    static List<Edge> adjList[];
    static StringBuilder ans = new StringBuilder();

    static class Edge {
        int to, dist;
        Edge(int to, int dist) {
            this.to = to;
            this.dist = dist;
        }
    }
    private static void input() throws IOException {
        stk = new StringTokenizer(br.readLine());
        N = Integer.parseInt(stk.nextToken());
        M = Integer.parseInt(stk.nextToken());
        adjList = new ArrayList[N+1];
        for(int i=1; i<=N; i++) {
            adjList[i] = new ArrayList<>();
        }
        dist = new int[N+1][N+1];
        p = new int[N+1][N+1];
        for(int i=1; i<=N; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }

        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                p[i][j] = j;
            }
        }
        for(int i=0; i<M; i++) {
            stk = new StringTokenizer(br.readLine());
            int st = Integer.parseInt(stk.nextToken());
            int ed = Integer.parseInt(stk.nextToken());
            int dist = Integer.parseInt(stk.nextToken());
            adjList[st].add(new Edge(ed,dist));
            adjList[ed].add(new Edge(st,dist));
        }
    }

    private static void solve() {
        for(int i=1; i<=N; i++) {
            dijstra(i);
        }
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                if(i==j) ans.append("- ");
                else ans.append(find(i, j)).append(" ");
            }
            ans.append("\n");
        }
    }

    private static void dijstra(int idx) {
        PriorityQueue<Edge> pq = new PriorityQueue<>((e1, e2)->e1.dist-e2.dist);
        pq.add(new Edge(idx, 0));
        dist[idx][idx] = 0;
        while(!pq.isEmpty()) {
            Edge curr = pq.poll();
            if(curr.dist > dist[idx][curr.to]) continue;
            for(Edge next : adjList[curr.to]) {
                if(dist[idx][next.to] > dist[idx][curr.to]+next.dist) {
                    dist[idx][next.to] = dist[idx][curr.to]+next.dist;
                    p[idx][next.to] = curr.to;
                    pq.add(new Edge(next.to, dist[idx][next.to]));
                }
            }
        }
    }

    private static void output() {
        System.out.println(ans);
    }

    private static int find(int i, int j) {
        if(i==p[i][j]) return j;
        return find(i, p[i][j]);
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
        output();
    }
}

플로이드-워셜

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

public class Main2 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer stk;
    static int N, M, adj_arr[][], p[][];
    static StringBuilder sb = new StringBuilder();
    static final int MAX = (int)4e8+4;

    private static void input() throws IOException {
        stk = new StringTokenizer(br.readLine());
        N = Integer.parseInt(stk.nextToken());
        M = Integer.parseInt(stk.nextToken());
        adj_arr = new int[N + 1][N + 1];
        p = new int[N + 1][N + 1];

        for (int i = 1; i <= N; i++) {
            for(int j=1; j<=N; j++) {
                if(i==j) adj_arr[i][j] = 0;
                else adj_arr[i][j] = MAX;
                p[i][j] = j;
            }
        }

        for (int i = 0; i < M; i++) {
            stk = new StringTokenizer(br.readLine());
            int st = Integer.parseInt(stk.nextToken());
            int ed = Integer.parseInt(stk.nextToken());
            int dist = Integer.parseInt(stk.nextToken());
            adj_arr[st][ed] = dist;
						adj_arr[ed][st] = dist;
        }
    }

    private static void floyd_warshall() {
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (adj_arr[i][j] > adj_arr[i][k] + adj_arr[k][j]) {
                        adj_arr[i][j] = adj_arr[i][k] + adj_arr[k][j];
                        p[i][j] = p[i][k];
                    }
                }
            }
        }
    }

    private static void output() {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (i == j) sb.append("- ");
                else sb.append(p[i][j]).append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }

    public static void main(String[] args) throws IOException {
        input();
        floyd_warshall();
        output();
    }
}