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

문제

풀이

딱 보고 노드사이의 거리는 다익스트란데? 하면서
최단경로(https://www.acmicpc.net/problem/1753)
문제가 떠올랐다.

차이점은 여러 노드에서의 최단경로를 구해야하는 것
그래서 시간복잡도를 계산하여봤다.
다익스트라의 시간복잡도는 O(ElogV) (https://funny-gourd-490.notion.site/2c7b1dd90e9f4fe09fa8216a8db3eeb6)
이므로 O(NlogN) 을 M번 반복하여 = O(1000log1000*1000) = 10^7이므로 시간초과가 나지 않을 것이라 생각하고 문제를 풀었다.

일단 입력으로 받은 노드의 정보를 배열로 저장하고
최단 경로를 구해야하는 시작점과 끝점을 입력받아 dijkstra() 메소드에 넣고 정답을 출력하였다.

코드

static class Node{
    int edge;
    int weight;

    public Node(int edge, int weight) {
        this.edge = edge;
        this.weight = weight;
    }
}

노드 클래스를 정의해논 곳이다.
Graph[i] 배열에 i는 노드의 자기자신이고 그 안에 Node(edge, weight)가 여러개 들어간다. 이는 그 Node()들과 연결되었다는 뜻이다. 연결된 노드가 몇개인지 알 수 없으므로 ArrayList를 이용해 크기가 유동적인 List를 활용한다. edge는 노드의 번호, weight는 거리(가중치)이다.
static ArrayList<Node>[] graph;
for문을 돌려 초기화 시켜주는 것을 잊지말자

// 초기화
for (int i = 1; i <= N; i++) {
   graph[i] = new ArrayList<>();
}
// 초기화 끝

다익스트라 함수

public static int dijkstra(int start, int end) {
    dist = new int[N+1];
    for (int i = 1; i <= N; i++) {
        dist[i] = INF;
    }
    visit = new boolean[N+1];

    PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.weight));
    pq.add(new Node(start, 0));
    dist[start] = 0;
    visit[start] = true;

    while (!pq.isEmpty()) {
        Node curNode = pq.poll();

        // node 순회
        for (Node next : graph[curNode.edge]) {
            if(visit[next.edge]) continue;
            if(dist[next.edge] < next.weight + curNode.weight) continue;
            dist[next.edge] = next.weight + curNode.weight;
            pq.add(new Node(next.edge, dist[next.edge]));
            visit[next.edge] = true;
        }
    }

    return dist[end];
}

다익스트라는 PriorityQueue를 이용해 최단경로를 빠르게 구하는 알고리즘이다.
visit[] 배열과
dist[] 배열을 활용해야 한다

• visit[] - 다익스트라가 한 번 갔던 노드를 재반복하지 않도록 저장
• dist[] - start노드에서 각 노드까지의 거리를 저장하는 배열이다
  - 모든 노드의 거리를 최대값(INF)로, 자신은 0으로 초기화하고 시작한다
  

PriorityQueue에 들어오면 weight가 작은 차례로 끄집어 내면서 그 노드가 갈 수 있는(연결된, graph[]에서 갖고있는) 노드들을 순회한다.
만약 방문했던 node라면 pass하고
방문할 노드가 가치가 있다면 dist를 최신화 하고 PriorityQueue에 집어넣는다
가치가 있는지 확인하는 방법은 현재 노드까지 걸린 weight + 다음 노드 까지 가는 weight 값 < 내가 가지고 있는 다음 노드까지의 weight(dist[]) 일 경우이다.

전체코드

package baekjoon._1240;

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

public class Main {
    static int N, M;
    static ArrayList<Node>[] graph;
    static boolean[] visit;
    static int[] dist;
    static int INF = Integer.MAX_VALUE;
    static StringBuilder sb = new StringBuilder();

    public static void input() {
        FastReader fr = new FastReader();
        N = fr.nextInt();
        M = fr.nextInt();
        graph = new ArrayList[N+1];
        // 초기화
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }
        // 초기화 끝
        for (int i = 0; i < N-1; i++) {
            int n = fr.nextInt(); // start
            int m = fr.nextInt(); // end
            int k = fr.nextInt(); // weight
            graph[n].add(new Node(m, k));
            graph[m].add(new Node(n, k));
        }
        for (int i = 0; i < M; i++) {
            int start = fr.nextInt();
            int end = fr.nextInt();
            sb.append(dijkstra(start, end));
            sb.append("\n");
        }
    }

    public static void main(String[] args) {
        input();
        System.out.println(sb);
    }

    public static int dijkstra(int start, int end) {
        dist = new int[N+1];
        for (int i = 1; i <= N; i++) {
            dist[i] = INF;
        }
        visit = new boolean[N+1];

        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.weight));
        pq.add(new Node(start, 0));
        dist[start] = 0;
        visit[start] = true;

        while (!pq.isEmpty()) {
            Node curNode = pq.poll();

            // node 순회
            for (Node next : graph[curNode.edge]) {
                if(visit[next.edge]) continue;
                if(dist[next.edge] < next.weight + curNode.weight) continue;
                dist[next.edge] = next.weight + curNode.weight;
                pq.add(new Node(next.edge, dist[next.edge]));
                visit[next.edge] = true;
            }
        }

        return dist[end];
    }

    static class Node{
        int edge;
        int weight;

        public Node(int edge, int weight) {
            this.edge = edge;
            this.weight = weight;
        }
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader(){ br = new BufferedReader(new InputStreamReader(System.in));}

        String next(){
            while(st == null || !st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() { return Integer.parseInt(next()); }

        long nextLong() { return Long.parseLong(next()); }

        Double nextDouble() { return Double.parseDouble(next()); }

        String nextLine(){
            String str = "";
            try{
                str = br.readLine();
            } catch(IOException e){
                e.printStackTrace();
            }
            return str;
        }
    }
}

느낀점

분명 계획대로 풀었는데 자꾸 정답이 나오지 않고 INF값이 나오길래 디버깅 해봤더니 입력으로 받은 간선정보를 한 방향으로만 적용해 다익스트라가 중간에 끊겨버렸었다. 양방향으로 해주니 바로 정답이 나왔다.

PriorityQueue를 사용하는 이유

• 노드의 방문 순서 결정: 다익스트라 알고리즘은 출발 노드에서부터 거리가 짧은 노드를 우선적으로 방문하며, 그 노드를 거쳐서 다른 노드에 도달하는 거리를 계산합니다. 이를 위해 PriorityQueue를 사용하여 노드를 우선순위에 따라 방문 순서를 결정합니다.
• 최단 거리 갱신: PriorityQueue를 사용하면 노드를 우선순위에 따라 처리하기 때문에, 먼저 처리된 노드의 최단 거리가 갱신되면, 이에 연결된 다른 노드의 최단 거리를 재계산하고 우선순위 큐에 다시 추가합니다. 이를 통해 노드의 거리를 효율적으로 갱신할 수 있습니다.
• 시간 복잡도: 일반적으로 다익스트라 알고리즘에서 우선순위 큐를 사용하면 시간 복잡도가 더 효율적이며, O(E log V)의 시간 복잡도를 가집니다.
  따라서, PriorityQueue를 사용하면 다익스트라 알고리즘을 빠르고 효율적으로 구현할 수 있으며, 최단 경로를 빠르게 계산할 수 있습니다.