[BOJ] 1719. 택배

[작성일]

• 2022-02-22

[분류]

• 다익스트라
• 플로이드-와샬
  
  
  

[문제링크]

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

[요구사항]

• 휴게소와 휴게소 사이 거리 중에서 최댓값을 가장 작은 값이 되도록 휴게소를 더 세우고 답을 출력하라.
  
  
  

[풀이]

모든 노드에 대한 최단경로를 구해야하기 때문에 처음에 플로이드-와샬로 풀었다.
그리고 모든 노드에 대해서 다익스트라를 돌려서 구하는 방법도 있길래 참고해서 또 풀어보았다.

1) 플로이드-와샬 방법
플로이드 와샬은 기본적으로 for문을 3중첩해서 사용한다.
원리는 i~j사이의 최소 거리를 구하는데에 i~k + k~j 한 것과 비교해서 계속해서 갱신해나가는 방식이다. 그대로 구현하면 된다.
가장 처음 방문하는 노드의 경우 저장할 수 있는 vertex 이차원 배열을 만들고 최소 거리가 갱신될 때마다 vertex[i][j] = vertex[i][k]로 갱신해나간다. 그러면 계속 가지고 갈 수 있다.

2) 다익스트라 방법
다익스트라는 우선 배열리스트를 이용해 그래프부터 생성한다.
다익스트라는 하나의 start점을 정해놓고 나머지 도착점에 대해서 걸리는 최소 경로를 구하는 방법이다. 따라서, start점 하나에 대해서는 O(V^2)이 된다. 하지만 다음에 볼 좌표를 결정하는 과정에서 최소힙을 사용하면 O(ElogV)로 개선가능하다.
우선순위 큐를 이용해서 다익스트라 과정을 진행하면서 최소 거리가 갱신될 때마다 path 배열에 경로상의 node를 저장한다. 이후 마지막에 재귀로 경로를 거슬러 올라가서 맨 처음 방문한 노드 값을 결과String에 추가해준다.

[코드 - 플로이드-와샬]

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

// 1. 모든 전체쌍 최단경로이므로 플로이드-와샬
public class Main {
    static int N, M;
    static int[][] graph;
    static int[][] vertex;

    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());

        graph = new int[N + 1][N + 1];
        vertex = new int[N + 1][N + 1];
        for (int i = 0; i <= N; i++) {
            Arrays.fill(graph[i], 10001);
        }
        for (int i = 1; i <= N; i++) {
            graph[i][i] = 0;
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            graph[a][b] = w;
            graph[b][a] = w;
            vertex[a][b] = b;
            vertex[b][a] = a;
        }

        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (graph[i][j] > graph[i][k] + graph[k][j]) {
                        graph[i][j] = graph[i][k] + graph[k][j];
                        vertex[i][j] = vertex[i][k];
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (i == j) {
                    sb.append("- ");
                } else {
                    sb.append(vertex[i][j] + " ");
                }
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
}

[코드 - 다익스트라]

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

public class Main {
    static int N, M;
    static ArrayList<Edge>[] list;
    static StringBuilder sb = new StringBuilder();
    static int[] distance;
    static int[] path;

    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());
        // 다익스트라는 배열리스트로 구현하는게 좋기 때문에 리스트 생성
        list = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            list[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            list[from].add(new Edge(to, w));
            list[to].add(new Edge(from, w));
        }

        // 모든 vertex에 대해서 다익스트라 수행
        for (int i = 1; i <= N; i++) {
            distance = new int[N + 1];
            path = new int[N + 1];
            Arrays.fill(distance, 10001);
            dijkstra(i);
        }

        System.out.println(sb);
    }

    public static void dijkstra(int start) {
        distance[start] = 0;
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.add(new Edge(start, 0));
        while (!pq.isEmpty()) {
            Edge now = pq.poll();

            if (now.cost > distance[now.node]) continue;

            for (Edge next : list[now.node]) {
                if (distance[next.node] > distance[now.node] + next.cost) {
                    distance[next.node] = distance[now.node] + next.cost;
                    pq.add(new Edge(next.node, distance[next.node]));
                    path[next.node] = now.node;
                }
            }
        }

        // 재귀로 경로 거슬러 올라가며 찾아서 넣어주기
        for (int i = 1; i <= N; i++) {
            if (i == start) sb.append("- ");
            else {
                sb.append(find(i, start) + " ");
            }
        }
        sb.append("\n");
    }

    public static int find(int i, int start) {
        if (path[i] == start) return i;
        return find(path[i], start);
    }
}

class Edge implements Comparable<Edge> {
    int node;
    int cost;

    public Edge(int node, int cost) {
        this.node = node;
        this.cost = cost;
    }

    @Override
    public int compareTo(Edge e) {
        return this.cost - e.cost;
    }
}

[느낀점]

모든 노드에 대한 값을 구해야해서 무조건 플로이드-와샬로만 생각했는데 다익스트라로도 시도해보는 습관을 들여야겠다.