백준 1753 최단경로

유명한 문제.

우선순위 큐, 인접 리스트, 너비 우선 탐색, 다익스트라 등 공부한 것이 많은 문제였다.

그래프의 최단거리를 탐색하면 되는데 간선의 가중치가 존재한다.

다익스트라 과정

그림 못그림

위의 그림은 단방향 그래프이다

다익스트라는 거리에 대한 초기값을 무한대로 초기화 해놓는다.

1번을 탐색 시작 정점이라고 했을 때, 1번 정점을 방문처리를 해준다.

일반적인 bfs는 큐에 넣을 때 방문처리를 하는 경우가 많은데 다익스트라를 사용할 때는 큐에서 꺼낼 때 방문처리를 해줘야 한다(물론 visited 없이도 풀 수 있다)

기존 거리보다 짧은 최단거리가 나온다면 계속 거리를 갱신해줘야 하는데 큐에 넣을 때 방문 처리 해주면 갱신하지 못하는 경우가 발생한다.

1번에서 간선이 존재하는(자신 포함) 정점의 거리를 초기화 해주면서 우선순위 queue에 넣어줘서 다음 탐색에 방문할 후보로 넣어준다.

우선순위 큐는 node클래스의 거리를 비교하여 더 작은 거리를 가진 node가 나올 수 있게 했다.

방문노드 1

 

정점	1	2	3	4	5
거리	0	1	3	INF	INF

 

1에서 갈 수 있는 정점은 2와 3이고 그 둘의 거리가 1, 3으로 바꼈다. 거리 갱신은 현재 노드 + 간선

그리고 다음 탐색 노드를 정하는데, 탐색 시점 기준 거리가 가장 짧은 노드를 선택한다.

표를 기준으로는 2번 노드가 거리 1로 가장 짧기 때문에 2를 방문노드로 선정한다.

우선순위 큐를 사용한 이유인데, 그냥 꺼내면 거리가 가장 짧은 2번 node가 나오게 된다.

방문 노드 2

 

정점	1	2	3	4	5
거리	0	1	2	INF	5

 

2번 노드를 방문하고 앞선 과정을 반복해본다.

2번 노드를 현재 노드로 설정하고 방문처리 해준다.

2번에서 갈 수 있는 노드중에서 방문하지 않은 노드에 대해서 최소값을 비교해본다.

1은 2에서 갈 수 있지만 이미 방문했으니 초기화 되지 않는다.

1 -> 3으로 연결된 3의 비용을 지닌 간선보다 1->2의 거리인 1과 2->3의 거리인 1을 더한 2의 비용을 가진 루트가 더 짧은 것을 알게 된다.

그리고 2->4가 가능하니 4번 노드에 대한 거리가 2번노드 거리 1과 5번 노드 거리 4를 더한 5로 초기화 된다.

거리 배열은 아래와 같이 갱신된다.

방문 가능한 모든 노드를 큐에 넣어준다.

3번 노드도 다시 한번 큐에 들어가는데, 갱신된 거리와 함께 들어간다.

그러므로 지금 큐에 있는 노드를 (노드, 거리)로 작성하면

(3,2) (3, 3) (5, 5) 가 들어가 있을 것이다.

우선순위 큐를 통하면 2의 거리를 가진 3번 노드가 다음 방문 노드로 선정될것이다.

3번 노드를 방문 처리 해주고 탐색을 진행한다.

방문노드 3

 

정점	1	2	3	4	5
거리	0	1	2	6	3

 

같은 과정이니 짧게 설명하자면,

3에서 5번 노드로 가는 길이 이전 거리보다 짧기 때문에 갱신이 될 것이고, 4번 노드의 거리가 첫번째로 갱신이 된다.

큐에는 4번 5번 노드가 들어간다.

큐에는 이전에 들어가있던 (3, 3) (4, 5)와

(4, 6) (5, 3) 이 들어가서

(3, 3), (5, 3), (4, 5) (4, 6)이 들어가있다.

큐에서 값을 꺼내면 3의 거리를 가진 3번노드가 나올텐데 3번 노드는 이미 방문처리가 되어 있으므로 방문하지 않고

반복문을 통해 다시 값을 꺼내면 5번 노드가 나오게 된다.

5번노드는 방문할 수 있는 노드가 없으므로 다시 위의 과정을 반복하여 4번 노드가 나오고

4번 노드도 5번과 동일하게 조건문을 타지 않아서 결국 q.isEmpty = true가 되어 탐색이 끝나게 된다.

최종

 

정점	1	2	3	4	5
거리	0	1	2	6	3

 

내가 계속 실수했던 부분은, 갱신된 거리값을 가진 노드 객체를 큐에 넣어줘야 하는데, 간선값만을 지닌 객체를 넣어준 것이다.

그래서 오래걸렸다.

 

import java.util.*;
import java.io.*;


public class Main {
    static int nodeNum;
    static int[] distance;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        nodeNum = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());

        int startNode = Integer.parseInt(br.readLine());

        PriorityQueue<Node> q = new PriorityQueue<>();
        ArrayList<ArrayList<Node>> edge = new ArrayList<>();
        boolean[] visited = new boolean [nodeNum+1];
        distance = new int[nodeNum+1];

        for(int i = 1; i <= nodeNum; i++)
            distance[i] = Integer.MAX_VALUE;
        for(int i = 0; i <= nodeNum; i++)
            edge.add(new ArrayList<>());

        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            int w = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            edge.get(w).add(new Node(d, v));
        }
        q.add(new Node(startNode, 0));
        distance[startNode] = 0;
        Dijkstra(edge, distance, visited, q);
        for(int i = 1; i <= nodeNum; i++){
            if(!visited[i])
                System.out.println("INF");
            else
                System.out.println(distance[i]);
        }
    }

static void Dijkstra(ArrayList<ArrayList<Node>> edge, int[]distance, boolean[] visited, PriorityQueue<Node> q){

        while(!q.isEmpty()){        
            int node = q.poll().vertex;
            if(!visited[node]){
                visited[node] = true;
                for(int j = 1; j <= edge.get(node).size(); j++){
                    if(distance[node] + edge.get(node).get(j-1).value < distance[edge.get(node).get(j-1).vertex])
                        distance[edge.get(node).get(j-1).vertex] = distance[node] + edge.get(node).get(j-1).value;
                    q.add(new Node(edge.get(node).get(j-1).vertex, distance[edge.get(node).get(j-1).vertex]));
                }
            }
        }
    }
    
}

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

    public Node(int d, int v) {
        this.vertex = d;
        this.value = v;
    }

    @Override
    public int compareTo(Node p) {
        return this.value - p.value;
    }
}