[백준] 1916- 최소비용 구하기 문제 풀이(자바,Java)

문제

1916번: 최소비용 구하기

들어가며

다익스트라를 처음 배울 땐, visited 배열(노드 방문 처리)를 사용하지 않아도 된다고 배웠다.

근데 웬걸.. 바로 써야하는 문제를 만났다.

 

코드

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

public class 최소비용구하기_1916 {
    private static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
    private static int v, e;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        v = Integer.parseInt(br.readLine());
        e = Integer.parseInt(br.readLine());

        for (int i = 0; i < v; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < e; i++) {
            int[] s = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int start = s[0]-1;
            int end = s[1]-1;
            int weight = s[2];
            graph.get(start).add(new Node(end, weight));
        }
        int[] s = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int start = s[0];
        int end = s[1];
        dijkstra(start-1,end-1);
    }

    private static void dijkstra(int start, int end){
        PriorityQueue<Node> queue = new PriorityQueue<>();
        int[] dist = new int[v];
        Arrays.fill(dist, Integer.MAX_VALUE);

        boolean[] visited = new boolean[v];
        dist[start] = 0;
        queue.add(new Node(start,0));
        while (!queue.isEmpty()){
            Node current = queue.poll();
            if (visited[current.x]){
                continue;
            }
            visited[current.x] = true;
            for (var next : graph.get(current.x)){

                if (dist[next.x] > dist[current.x] + next.weight){
                    dist[next.x] = dist[current.x] + next.weight;
                    queue.add(new Node(next.x, dist[next.x]));
                }
            }
        }
        System.out.println(dist[end]);
    }

    static class Node implements Comparable<Node>{
        int x;
        int weight;

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

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

풀이

전형적인 다익스트라 문제이다.

두 정점에 사이의 최소 거리를 구하는데 모든 가중치가 양수이다.

이럴 때, 다익스트라를 쓰면 낮은 시간 복잡도로 문제를 풀 수 있다.

 

그러면 글 서두에 밝혔던 노드 방문 처리에 대해 이야기해보겠다.

먼저, 기본적인 다익스트라에선 노드 방문 처리는 필요가 없다.

왜냐하면 결국에 PQ가 최소 비용을 계속 뽑아 쓰기 때문에 결과를 연산하는덴 달라지지 않기 때문이다.

하지만 위 문제처럼 노드에 연결된 간선이 많아질 경우 이미 끝난 계산을 계속해서 할 경우의 수가 존재한다.

그래서 방문 처리를 하지 않으면 시간 초과가 발생한다.

 

왜 다익스트라 알고리즘에서 방문 처리를 해도 전혀 문제가 없을까?

다익스트라가 그리디 알고리즘에 기인하기 때문인데, PQ를 이용해서 항상 "현재까지의 최단 거리"를 가진 노드를 먼저 처리한다. 따라서 한 번 방문한 노드는 이미 최단 거리가 확정된 상태이기 때문에, 이후 해당 노드를 다시 탐색할 필요가 없다.

 

이 문제로 다시 돌아와보자.

우리는 도착 지점의 최단 거리가 확정되면 더 이상 탐색할 필요가 없다.

따라서, visited 배열을 사용하여 이미 방문한 노드를 건너뛰면 불필요한 연산이 줄어들고 시간 효율성이 높아진다.

 

결론 : 노드 방문 처리를 하자.