문제 설명

문제 분석

슈도코드

구현

public class 최단경로구하기_1753 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int V = scan.nextInt(); //노드의 개수
        int E = scan.nextInt(); //에지의 개수
        int K = scan.nextInt(); //출발 노드 번호
        boolean[] visited = new boolean[V+1]; //방문 배열
        int[] distance = new int[V+1]; //거리 배열
        List<Node>[] graph = new ArrayList[V + 1];
        for (int i = 0; i <= V; i++) {
            graph[i] = new ArrayList<>();
            distance[i] = Integer.MAX_VALUE;
        }

        //가중치가 있는 인접 리스트 초기화
        for (int i = 0; i < E; i++) {
            // u -> v로 가는 가중치 w
            int u = scan.nextInt();
            int v = scan.nextInt();
            int w = scan.nextInt();

            graph[u].add(new Node(v, w));
        }

        Queue<Node> q = new PriorityQueue<>();
        q.add(new Node(K, 0)); //K가 시작임
        distance[K] = 0;
        while(!q.isEmpty()) {
            Node curNode = q.poll();

            // 방문한 노드는 큐에 넣지 않음
            if(visited[curNode.target]) continue;

            visited[curNode.target] = true;
            for (Node nextNode : graph[curNode.target]) {
                int target = nextNode.target;
                int value = nextNode.value;
                // 최소 거리로 업데이트
                if(distance[target] > distance[curNode.target] + value) {
                    distance[target] = distance[curNode.target] + value;
                    q.add(new Node(target, distance[target]));
                }
            }

        }
    }
}

class Node implements Comparable<Node>{
    int target;
    int value;

    public Node(int target, int value) {
        this.target = target;
        this.value = value;
    }

    // 우선순위 큐 정렬 기준을 위함
    @Override
    public int compareTo(Node o) {
        if(this.value > o.value) return 1;

        return -1;
    }
}