1753번: 최단경로 [JAVA]

https://www.acmicpc.net/problem/1753

1753번: 최단경로

 

✔ 다익스트라

- 출발 노드와 모든 노드 간의 최단 거리 탐색

- 가중치는 모두 양수

- 시간복잡도: O(ElogV)

- 우선순위 큐(heap)을 사용해서 구현한다.

- '네비게이션'에 적용되는 알고리즘

 

 

접근 방식) 다익스트라

1. 도착 정점과 가중치 정보를 담을 Edge Class를 만든다.

2. 각 정점에 대해 Edge 객체에 대한 정보를 저장하기 위해, ArrayList<Edge>[] list를 만든다.

    시작 정점부터 모든 노드 간의 최단 거리를 저장할 int[] distance 생성

    방문 여부를 체크하기 위한 boolean[] visited 생성

    현재 최단 거리 배열에서 가중치 값이 가장 작은 노드를 가져오기 위해서 → 우선순위 큐 생성

    ⭐우선순위 큐의 정렬 기준을 정의해줘야 한다. (→ 가중치 기준으로 오름차순 정렬)

3. 입력 받은 시작 정점을 설정해준다.

→ 우선순위 큐에 add하고, 해당 정점의 최단 거리는 0으로 설정한다.

4. 우선순위 큐가 빌 때까지 반복문 수행하며, ArrayList<Edge>[] list를 이용해서

    현재 선택한 노드에 연결된 Edge를 탐색하며, 최단거리를 업데이트해준다.

5. 결과값 출력

    

package codingTestStudy.week4;

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

public class B_1753 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int V = Integer.parseInt(st.nextToken());   // 정점 개수
        int E = Integer.parseInt(st.nextToken());   // 간선 개수
        int startVertex = Integer.parseInt(br.readLine());

        ArrayList<Edge>[] list = new ArrayList[V + 1];
        int[] distance = new int[V + 1];            // 최단거리 기록
        boolean[] visited = new boolean[V + 1];     // 방문 여부
        PriorityQueue<Edge> pq = new PriorityQueue<>((e1, e2) -> {
            // 가중치 오름차순 정렬 정의
            return e1.weight - e2.weight;
        });

        for (int i = 1; i <= V; i++) {
            list[i] = new ArrayList<>();
            distance[i] = Integer.MAX_VALUE;
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            list[u].add(new Edge(v, w));
        }

        // 시작 정점 설정
        pq.add(new Edge(startVertex, 0));
        distance[startVertex] = 0;
        while (!pq.isEmpty()) {
            Edge now = pq.poll();
            int nowVertex = now.endVertex;

            if (visited[nowVertex]) continue;

            visited[nowVertex] = true;
            for (int i = 0; i < list[nowVertex].size(); i++) {
                Edge temp = list[nowVertex].get(i);
                int nextVertex = temp.endVertex;
                int weight = temp.weight;

                if (distance[nextVertex] > distance[nowVertex] + weight) {
                    distance[nextVertex] = distance[nowVertex] + weight;
                    pq.add(new Edge(nextVertex, distance[nextVertex]));
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= V; i++) {
            if (visited[i])
                sb.append(distance[i]).append('\n');
            else
                sb.append("INF").append('\n');
        }
        System.out.print(sb);
    }
}

class Edge {
    int endVertex;
    int weight;

    public Edge(int endVertex, int weight) {
        this.endVertex = endVertex;
        this.weight = weight;
    }
}