[알고리즘] 묘공단 다익스트라 알고리즘

문제 정보

graph배열은 노드의 연결정보와 가중치가 담겨있는 배열이고 start는 시작 노드의 번호가 있다.

n은 정수형으로 노드의 개수를 의미한다.

 

문제 설명

시작 노드를 포함한 모든 노드까지의 최단 거리를 순서대로 배열에 담아 리턴

 

입출력 예제

graph

{0, 1, 9}, {0, 2, 3}, {1, 0, 5}, {2, 1, 1}

 

start

0

 

n

3

 

result

{ 0, 4, 3 }

 

import java.util.*;
import java.util.stream.Collectors;

public class Solution {

    public static void main(String[] args) {
        for (int item : new Solution().solution(new int[][]{{0, 1, 9}, {0, 2, 3}, {1, 0, 5}, {2, 1, 1}}, 0, 3)) {
            System.out.println(item);
        }
    }
    public int[] solution(int [][] graph, int start, int n) {

        ArrayList<Node>[] adjust = new ArrayList[n];

        for (int i = 0; i < n; i++) {
            adjust[i] = new ArrayList<>();
        }

        // 각 노드에 연결된 노드 나열
        for (int[] edge : graph) {
            adjust[edge[0]].add(new Node(edge[1], edge[2]));
        }

        // 각 노드의 최소값을 설정하기 위한 배열
        int[] dist = new int[n];

        // 모든 노드의 거리 값을 무한대로 초기화
        Arrays.fill(dist, Integer.MAX_VALUE);

        // 시작 노드의 거리 값은 0으로 초기화
        dist[start] = 0;

        // 우선순위 큐 생성 후 시작 노드 넣기
        Queue<Node> pq = new ArrayDeque<>();

        pq.add(new Node(start, 0));

        while (!pq.isEmpty()) {

            Node now = pq.poll();

            // 이전 노드값이 현재 노드값 보다 큰경우 방문 했다는 의미이므로 패스
            if (dist[now.dest] < now.cost) {
                continue;
            }

            // 인접 노드 거리 계산 하여 업데이트
            for (Node next : adjust[now.dest]) {
				
                // 현재 노드 위치에서 더 작은 가중치인 경우 큐에 담는다.
                if (dist[next.dest] > now.cost + next.cost) {
                    dist[next.dest] = now.cost + next.cost;
                    pq.add(new Node(next.dest, dist[next.dest]));
                }
            }
        }
        return dist;

    }

        public static class Node {

            // 노드 번호
            int dest;

            // 가중치
            int cost;

            public Node(int dest, int cost) {
                this.dest = dest;
                this.cost = cost;
            }
        }
    }