[백준] BOJ 1719 택배 (골드 3)

문제

---

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

1719: 택배

---

해설

---

1. A -> B로 가는 최단 경로일 때 처음으로 방문해야하는 정점을 인접행렬 형식으로 출력해야한다.
2. 이를 위해 기본적으로 다익스트라를 통해 최단 경로를 구하는 로직을 구현하였다.
3. 이때, 처음 방문하는 정점의 번호를 기억하기 위해 Node에 first라는 변수를 추가적으로 선언한다.
4. 또한, 최종적으로 출력하기 위해 dist[N][M][2]형태로 최단 경로 비용을 저장하는 3차원 배열을 만든다.
   → 이때 마지막 차원은 [0] : 비용, [1] : 첫 방문 정점을 저장하도록 한다.
5. 이를 통해 dist[i][j][0]을 기본적으로 다익스트라 최단 경로 계산으로 사용한다.
6. 만약 다익스트라 로직에 따라 최단 경로가 갱신됐을 때 출발 노드가 아닌 경우라면 node.first (첫 방문 정점)을 설정하고, 이를 지속적으로 넘겨주는 방식으로 이를 관리하였다.ex) 1 -> 2 -> 5가 최단 경로라면 vertex = 1, 이며 node.vertex = 1이다. 따라서 n.first = 2를 first로 세팅해준다.
   2 -> 5는 vertex = 1이며 node.first = 2로 2를 그대로 받아서 넘겨준다.

   int first = node.first == vertex ? n.first : node.first;
   //dist도 출력을 위해 세팅
   dist[vertex][n.vertex][1] = first;
   //여기서 first 정점을 계속 넘겨주는 방식
   pq.offer(new Node(n.vertex, cost, first, null));

7. 이렇게 모든 정점을 시작점으로 하여 다익스트라를 진행하고, 최종적으로 dist[i][j][1]을 출력한다.

---

코드 (다익스트라)

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BOJ1719 {

    static int[][][] dist;
    static Node[] adjList;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        //from -> to 으로 가는 경로에서 상태 저장
        dist = new int[N + 1][N + 1][2]; // 0 : 거리, 1 : 첫 방문 집하장
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                dist[i][j] = new int[]{(Integer.MAX_VALUE / 2), j};
            }
        }

        adjList = new Node[N + 1];
        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 cost = Integer.parseInt(st.nextToken());
            adjList[from] = new Node(to, cost, to, adjList[from]);
            adjList[to] = new Node(from, cost, from, adjList[to]);
        }
        for (int i = 1; i <= N; i++) {
            dijkstra(i);
        }

        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(dist[i][j][1] + " ");
                }
            }
            sb.append("\n");
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static void dijkstra(int vertex) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(vertex, 0, vertex,null));
        dist[vertex][vertex] = new int[]{0, vertex};
        while (!pq.isEmpty()) {
            Node node = pq.poll();

            if(dist[vertex][node.vertex][0] < node.cost) continue;

            for (Node n = adjList[node.vertex]; n != null; n = n.next) {
                if (dist[vertex][n.vertex][0] > dist[vertex][node.vertex][0] + n.cost) {
                    int cost = dist[vertex][node.vertex][0] + n.cost;
                    dist[vertex][n.vertex][0] = cost;
                    int first = node.first == vertex ? n.first : node.first;
                    dist[vertex][n.vertex][1] = first;
                    pq.offer(new Node(n.vertex, cost, first, null));
                }
            }
        }
    }
}

class Node implements Comparable<Node> {
    int vertex, cost, first;
    Node next;

    public Node(int vertex, int cost, int first, Node next) {
        this.vertex = vertex;
        this.cost = cost;
        this.first = first;
        this.next = next;
    }

    @Override
    public int compareTo(Node o) {
        return Integer.compare(this.cost, o.cost);
    }
}

---

결론

---

다익스트라에서 인접 리스트를 링크드 리스트로 직접 구현하는 방법은 항상 잘 익혀둔 것 같다는 생각을 한다!

---