[Java/BOJ] 1753번: 최단경로

문제

---

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

 

입력

---

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

 

출력

---

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

 

풀이

---

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

: 그래프 상, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다.

알고리즘 동작 중에서, 도착 노드 뿐만 아니라 모든 다른 노드까지 최단 경로로 방문하며

각 노드까지의 최단 경로를 모두 찾게 된다.

매번 최단 경로의 노드를 선택해 탐색을 반복하는 것이다.

 

알고리즘 단계

1. 출발 노드와 도착 노드를 설정한다.

2. 거리 배열을 초기화한다. 시작 노드의 거리는 0, 나머지 노드는 무한대를 뜻하는 INF로 초기화한다.

3. 현 노드의 인접 노드 중에서 방문하지 않은 노드를 구별한다. 그 중에서 가중치가 가장 작은 노드를 선택하여 해당 노드를 방문 처리한다.

4. 해당 노드를 거쳐 다른 노드로 넘어가는 가중치를 계산하여 최단 거리 배열을 업데이트한다.

5. 모든 노드를 처리할 때까지, 2 ~ 4 단계를 반복한다.

 

4번 단계에서 이해가 잘 안 되었는데,

이를 더 설명해보겠다.

시작이 1이고 끝이 6인 그래프가 있으면,

방문하지 않은 노드 집합은 Before의 B, 방문한 노드의 집합은 After의 A,

최단 거리 배열은 Distance의 D라는 이름으로 배열을 지정한다.

B = { 1, 2, 3, 4, 5, 6 }

A = { }

D[1] = 0

D[2] = INF

D[3] = INF

D[4] = INF

D[5] = INF

D[6] = INF

텍스트와 구분하기 위해 코드블럭에 첨부하였다.

아무튼 초기값은 이 상태로 시작이 된다.

여기서, 시작 노드는 1이라서 D[1] = 0으로 지정하고 시작한다.

 

B = { 2, 3, 4, 5, 6 }

A = { 1 }

D[1] = 0

D[2] = 2

D[3] = 5

D[4] = 3

D[5] = INF

D[6] = INF

시작노드인 1을 방문 처리하고, 인접한 노드의 가중치를 최단 거리 배열에 업데이트한다.

 

방문하지 않은 노드 중(1과 근접한 노드인 2, 3, 4 중)에서 가중치가 가장 적은 노드는

2이다. 따라서 2 노드를 방문한다.

 

2 노드에서도 인접한 노드의 가중치를 최단 거리 배열에 업데이트한다.

예를 들어, 3노드로 예를 들어보자.

2 노드의 가중치인 2에서 +7이 된 9가 2 노드 기준의 3 노드의 가중치이다.

하지만, 최단 거리 배열에 있는 5보다 큰 수이기 때문에 업데이트 하지 않는다.

 

즉, 기존 배열에 있는 값보다 작은 값일 때만 업데이트한다.

 

B = { 2, 3, 4, 5, 6 }

A = { 1 }

D[1] = 0

D[2] = 2

D[3] = 5

D[4] = 3

D[5] = INF

D[6] = 12

2 노드를 방문 처리한 후의 상태이다.

그 다음 방문할 노드는 2 노드와 인접한 노드 중에서 가중치가 적은 노드가 아니라,

아까 1 노드에서 인접한 노드 중 2번째로 가중치가 적은 노드에 방문한다.

즉, 한 노드에서 가중치가 적은 순서대로 접근하여 최단 거리 배열을 계산한다.

 

이런 식으로 모든 노드가 방문 처리될 때까지 반복한다.

그럼 결과적으로 나오는 배열의 상태는 아래와 같다.

B = { 2, 3, 4, 5, 6 }

A = { 1 }

D[1] = 0

D[2] = 2

D[3] = 4

D[4] = 3

D[5] = 6

D[6] = 8

 

코드

---

import java.util.*;

public class Main {
    static final int INF = Integer.MAX_VALUE;

    static class Edge implements Comparable<Edge> {
        int vertex;  // 간선의 도착 정점
        int weight;  // 간선의 가중치

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

        @Override
        public int compareTo(Edge other) {
            return Integer.compare(this.weight, other.weight);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int V = scanner.nextInt();  // 정점의 개수 V
        int E = scanner.nextInt();  // 간선의 개수 E
        int startVertex = scanner.nextInt();  // 시작 정점

        // 그래프를 인접 리스트로 표현
        List<List<Edge>> graph = new ArrayList<>();
        for (int i = 0; i <= V; i++) {
            graph.add(new ArrayList<>());
        }

        // 간선 정보 입력
        for (int i = 0; i < E; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            int w = scanner.nextInt();
            graph.get(u).add(new Edge(v, w));
        }

        // 최단 거리를 저장할 배열
        int[] distance = new int[V + 1];
        Arrays.fill(distance, INF);  // 초기값은 무한대로 설정
        distance[startVertex] = 0;  // 시작 정점의 거리는 0

        // 우선순위 큐를 사용하여 최단 경로 찾기
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.offer(new Edge(startVertex, 0));

        while (!pq.isEmpty()) {
            Edge currentEdge = pq.poll();
            int currentVertex = currentEdge.vertex;
            int currentWeight = currentEdge.weight;

            // 이미 처리된 정점이면 무시
            if (currentWeight > distance[currentVertex])
                continue;

            // 현재 정점과 연결된 다른 정점들의 거리 업데이트
            for (Edge neighbor : graph.get(currentVertex)) {
                int neighborVertex = neighbor.vertex;
                int neighborWeight = neighbor.weight + currentWeight;

                // 더 짧은 경로를 발견한 경우 업데이트
                if (neighborWeight < distance[neighborVertex]) {
                    distance[neighborVertex] = neighborWeight;
                    pq.offer(new Edge(neighborVertex, neighborWeight));
                }
            }
        }

        // 최단 거리 출력
        for (int i = 1; i <= V; i++) {
            if (distance[i] == INF)
                System.out.println("INF");
            else
                System.out.println(distance[i]);
        }
    }
}