프로그래머스_부대복귀(Java)

다익스트라(Dijkstra) 알고리즘

주어진 그래프에서 하나의 출발점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘

이 알고리즘은 모든 가중치가 양수인 그래프에서 사용
출발점으로부터의 거리가 가장 짧은 정점을 선택하며, 이를 방문하여 해당 정점과 연결된 간선을 검토

출발점을 통해 해당 정점으로 가는 거리가 기존보다 더 짧을 경우, 거리를 업데이트하는 방식으로 최단경로 계산
시간 복잡도는 O((V + E) log V) (V: 정점의 수, E: 간선의 수)

 

답안 : 

 

public int[] solution(int n, int[][] roads, int[] sources, int destination) {
    int INF = 9_999_999; // 무한
    int[] answer = new int[sources.length];
 
    // 인접 리스트 생성
    List<Node>[] list = new ArrayList[n + 1];
    for (int i = 1; i <= n; i++) {
        list[i] = new ArrayList<>();
    }
    // 경로 정보(roads)를 통해 인접 리스트 초기화
    for (int i = 0; i < roads.length; i++) {
        int start = roads[i][0];
        int end = roads[i][1];
        list[start].add(new Node(end, 1));
        list[end].add(new Node(start, 1));
    }
 
    // 최단 거리 테이블 생성 및 초기화
    int[] shortest = new int[n + 1];
    for (int i = 0; i <= n; i++) {
        shortest[i] = INF;
    }
 
    PriorityQueue<Node> priorityQueue = new PriorityQueue<>((o1, o2) -> {
        if (o1.cost == o2.cost) {
            return o1.node - o2.node;
        }
        return o1.cost - o2.cost;
    });
    // 각 지역 방문 여부 체크 테이블
    boolean[] visited = new boolean[n + 1];
    priorityQueue.add(new Node(destination, 0));
    shortest[destination] = 0;
 
    while (!priorityQueue.isEmpty()) {
        Node poll = priorityQueue.poll();
        int now = poll.node;
 
        // 방문하지 않았다면 수행
        if (!visited[now]) {
            // 현재 노드 방문 처리
            visited[now] = true;
 
            int size = list[now].size();
            for (int i = 0; i < size; i++) {
                Node node = list[now].get(i);
 
                int pathNodeCost = node.cost;
                if (now != node.node && pathNodeCost != INF) {
                    int fullCost = poll.cost + pathNodeCost;
                    shortest[node.node] = Math.min(shortest[node.node], fullCost);
                    priorityQueue.add(new Node(node.node, fullCost));
                }
            }
        }
    }
 
    for (int i = 0; i < sources.length; i++) {
        int source = sources[i];
        // 문제 요구사항. 복귀가 불가능하다면(INF) -1로 반환
        int a = shortest[source] == INF ? -1 : shortest[source];
        answer[i] = a;
    }
 
    return answer;
}
 
private static class Node {
    public int node; // 지역 번호
    public int cost; // 이동 비용
 
    public Node(int node, int cost) {
        this.node = node;
        this.cost = cost;
    }
}