[Programmers] 부대복귀

문제 링크

프로그래머스-부대복귀

문제

다익스트라 알고리즘을 알고 있다면 쉽게 풀이방법을 떠올릴 수 있는 문제이다.

sources 배열에 주어진 위치에서 destination 까지 도달하는 최단 시간을 각각 구해서 반환해야한다.
이는 반대로 생각하면 destination에서 각 sources의 요소들에 도달하는데 걸리는 최단시간을 구하는 것이다.

후자가 적합한 이유는 a에서 b에 도달하는 최단시간을 구하기 위해서는 그 과정에서 거치는 모든 지점을 탐색하게 된다.
즉 sources각 원소를 시작점으로 잡고 destination까지의 최단거리를 구하면 그 과정에서 불필요한 탐색이 늘어나고 시간복잡도가 증가한다. 따라서 destination을 시작점으로 다익스트라 알고리즘을 사용하여, 모든 지점에 대한 최단시간을 구한다. 이후 sources의 원소들에 대한 시간을 answer에 담아 반환한다.

java로 코드를 작성하다보니 cpp에서 쉽게 작성하던 부분들도 버벅였다. 배열을 선언하고 우선순위 큐를 사용하는 것, 특히 pair자료구조가 java에는 존재하지 않아서 클래스를 따로 선언하는 등 번거롭다고 느껴지는 게 있었다.
PriorityQueue의 비교연산자를 선언해주는 것은 훨씬 간단하긴 했다. 또 배열의 값을 초기화하는 등 인덱스를 깊게 생각하지 않고 편리하게 사용할 수 있는 점은 좋은 것 같다.
java로 다른 사람이 짠 코드를 보니 훨씬 깔끔하고 내 코드에 불필요한 부분이 많음을 느꼈다. 언어에 조금 더 익숙해지려고 노력해야겠다.

우선순위 큐를 사용하는 이유

일반 Queue와 PriorityQueue 둘 중 어떤 것을 사용하더라도 다익스트라 알고리즘을 구현할 수 있다.

하지만 이 두 자료구조의 사용에는 시간복잡도의 차이가 존재한다.
우선순위 큐를 사용할 경우에는 노드를 처음 방문할 때 거리가 최소값임을 보장한다. 즉 어떤 노드 n에 처음 방문하고 n에서 도착 가능한 지점들을 모두 확인하고 거리값을 계산해 PriorityQueue에 넣었다면, 다시는 n에 방문하고 n에서 시작해 도착할 수 있는 지점들의 값을 계산할 필요가 없다. 첫 방문이 n까지의 최단거리이고, 이는 n에 인접한 노드들까지 n을 거쳐 도착할 수 있는 최단거리도 계산이 완료된 상태라는 것을 의미하기 때문이다.

Dijkstra 알고리즘과 실행시간(Priority Queue를 사용하는 이유)

코드

import java.util.*;


class Solution {
    public int[] solution(int n, int[][] roads, int[] sources, int destination) {
        int[] answer = new int[sources.length];
        int[] dist = new int[n+1];
        
        ArrayList<ArrayList<Integer>> G = new ArrayList<>();
        for(int i=0; i<=n; i++) G.add(new ArrayList<>());

        for(int i=0; i<roads.length; i++){
            int a = roads[i][0]; int b = roads[i][1];
            G.get(a).add(b);
            G.get(b).add(a);
        }

        PriorityQueue<Node> pq = new PriorityQueue<>(roads.length, Comparator.comparingInt(node->node.weight));
        Arrays.fill(dist,101010);
        dist[destination] = 0;
        
        pq.add(new Node(destination, 0));

        while(!pq.isEmpty()){
            Node node = pq.poll();
            int now = node.vertex;
            int w = node.weight;

            for(int i =0; i<G.get(now).size(); i++){
                if(dist[G.get(now).get(i)]> w + 1){
                    dist[G.get(now).get(i)] = w+1;
                    pq.add(new Node(G.get(now).get(i), w+1));
                }
            }
        }

        for(int i=0; i<sources.length; i++){
            answer[i] =  (dist[sources[i]] < 101010) ? dist[sources[i]] : -1;
        }

        return answer;
    }

    static class Node {
        int vertex;
        int weight;

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

}