[백준] 1916 : 최소비용 구하기 (JAVA)

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

 

🚩다익스트라 (Dijkstra)

 

1916번 문제를 보자마자 기본적인 다익스트라 알고리즘으로 해결할 수 있겠다고 생각을 했습니다. 평소에 알고 있던 다익스트라 방식으로 구현을 진행했고, 예제 출력도 정상적으로 나왔기 때문에 정답 제출을 했는데요..

 

 

결과는 시간 초과입니다🥲

15% 지점에서 계속 시간 초과가 발생했고, 문제를 다시 확인해 보니 시간제한이 0.5초 인걸 확인할 수 있었습니다.

 

시간 복잡도를 개선하기 위해 코드 분석을 해봤지만 문제의 원인은 찾지 못했고 검색을 통해 해결책을 찾아보니, queue에서 poll() 연산을 수행할 때 해동 노드의 방문 여부를 확인하는 처리가 필요하다는 것을 알게 되었습니다.

 

'근데.. queue.add를 수행하기 전에 이미 방문 여부를 확인하고, 미방문을 노드만 추가하는데, 왜 poll() 시점에 다시 방문 처리를 해야 하는 걸까?'라는 의문이 들었습니다.

 

 

🤔 2번 방문 확인하는 이유는 뭐지..?

 

코드를 디버깅해본 결과, 아직 미방문 상태인 5번 노드에 대한 요청이 두 번 발생했고, 이로 인해 방문 PriorityQueue을 사용하고 있음에도 불구하고 동일한 노드에 대한 처리가 중복으로 수행되고 있었습니다.

 

이러한 중복 처리를 방지하고 실행 시간을 최적화하기 위해, poll() 연산 이후에 방문 여부를 한 번 더 확인하는 것이 필요했던 것입니다!

 

---

 

아래는 제출한 코드입니다.

import java.io.*;
import java.util.*;

class Node {
    int end;
    int weight;

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

public class Main {

    static ArrayList<Node>[] al;
    static int[] result;
    static boolean[] visited;

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

        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        al = new ArrayList[N + 1];
        result = new int[N + 1];
        visited = new boolean[N + 1];

        for (int i = 1; i <= N; i++) {
            al[i] = new ArrayList<>();
            result[i] = Integer.MAX_VALUE;
        }

        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 c = Integer.parseInt(st.nextToken());

            al[a].add(new Node(b, c));
        }

        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        result[start] = 0;
        djk(start);

        bw.write(result[end] + "");
        bw.close();
    }

    public static void djk(int start) {
        PriorityQueue<Node> queue = new PriorityQueue<>((o1, o2) -> o1.weight - o2.weight);
        queue.add(new Node(start, 0));

        while (!queue.isEmpty()) {
            Node now = queue.poll();

            if (visited[now.end]) continue;	// 추가한 코드

            for (Node next : al[now.end]) {
                if (!visited[next.end]) {
                    if (next.weight + result[now.end] < result[next.end]) {
                        result[next.end] = next.weight + result[now.end];
                        queue.add(new Node(next.end, result[next.end]));
                    }
                }
            }
            visited[now.end] = true;
        }
    }
}