BOJ_1753 : 최단경로

👉 문제링크

1753번: 최단경로

---

---

🔸 문제 분석 🔸

• 가중치가 있는 방향 그래프에서 시작 노드부터 다른 모든 노드까지의 최단 거리를 구한다.
  • 정점의 수 V, 간선의 수 E. 시작 노드 K와 연결 정보가 주어진다.
  • 가중치는 10 이하의 자연수이다.
• 다익스트라의 반복이나 프림 알고리즘으로 풀이할 수 있다.
  • 시작 노드에서 아직 방문하지 않은 인접 노드 중 최소 가중치 간선을 선택해 탐색한다.
    (갈 수 있는 간선 중 최소 값을 선택하면 최단거리가 보장된다)
  • 아직 방문하지 않은 노드의 최단거리는 무한대(INF)이지만,  -1로 표시한다.

🔸 코드 🔸

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    private static class Edge implements Comparable<Edge> {
        int node;
        int weight;

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

        @Override
        public int compareTo(Edge o) {
            return this.weight - o.weight;
        }
    }

    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(br.readLine());

        ArrayList<Edge>[] adjlist = new ArrayList[V + 1];
        for (int i = 1; i <= V; i++) {
            adjlist[i] = new ArrayList<>();
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            adjlist[Integer.parseInt(st.nextToken())].add(new Edge(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        // Prim
        int[] d = new int[V + 1];
        Arrays.fill(d, -1);

        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.add(new Edge(K, 0));

        while (!pq.isEmpty()) {
            Edge now = pq.poll();
            if (d[now.node] >= 0) continue;

            d[now.node] = now.weight;

            for (Edge e : adjlist[now.node]) {
                if (d[e.node] == -1) {
                    pq.add(new Edge(e.node, e.weight + now.weight));
                }
            }
        }

        // Output
        for (int i = 1; i <= V; i++) {
            if (d[i] == -1) sb.append("INF");
            else sb.append(d[i]);
            sb.append('\n');
        }

        bw.write(sb.toString());
        bw.flush();
    }
}

🔸 코드 해석 🔸

• 간선 정보에서 연결 노드와 가중치를 함께 저장하기 위해 클래스 Edge를 선언한다.
  • 목적지 노드는 node, 가중치는 weight로 저장한다. 
  • 우선순위 큐에 사용되므로 Comparable 인터페이스를 상속하고, compareTo 메서드를 오버라이드해서 대소 비교기준을 weight로 설정한다.
• 노드 수, 간선 수, 시작 노드, 간선 정보를 입력받는다.
• 각 노드의 최단거리를 저장할 int형 배열 d를 선언하고 -1로 초기화한다.
• 우선순위 큐에 시작 노드 K를 넣고, 가중치는 0으로 시작한다.
• 큐가 빌 때까지 계산을 반복한다.
  • 큐에서 Edge 객체를 하나 꺼낸다.
  • 이미 방문했으면 (가중치가 -1이 아니면) 다시 뽑는다.
  • 아직 방문하지 않았으면, 현재 가중치가 최단거리이므로 배열 d에 저장한다.
  • 인접한 노드 중 아직 방문하지 않는 노드까지의 가중치 정보를 우선순위 큐에 더한다.
• 배열 d를 한 줄씩 출력한다.
  • -1은 "INF"로 바꿔 출력한다.

---

🔸 end 🔸

• 시작 노드부터 다른 모든 노드까지의 최단거리는 바로 Prim알고리즘이라 생각해 쉽게 풀이할 수 있었다.
  • 백준에서는 Prim이 따로 없이 Dijkstra알고리즘으로 나타내는 것 같다.
  • 사실 거의 같은 개념이라 큰 차이는 없다고 생각각한다. 하지만, Prim은 연습이 많이 됐는데 Dijkstra는 아직 연습이 부족한 것 같다. 활용 문제에서 어려움이 많다.
• 문제의 분석과 풀이 전략을 적어가며 풀이했다.