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

문제 설명

 

문제 링크 : https://www.acmicpc.net/problem/1753

 

이 문제는 다익스트라 알고리즘을 사용할 줄 아는지 묻는 문제이다.

따라서 다익스트라 알고리즘을 코드로 구현만 해주면 된다.

 

간단하게 다익스트라 알고리즘을 알아보자.

 

만약 위와 같은 모양의 그래프가 있다고 가정해 보자.

그래프 문제에서 가중치가 있는 간선을 다룰 때는 인접 리스트를 표현할 때

클래스를 하나 생성하여 다음 정점과 해당 정점까지의 거리를 표현할 수 있다.

 

인접 리스트로 가중치가 있는 그래프를 표현한다면

위와 같이 표현할 수 있을 것이다.

 

이제 다익스트라 알고리즘을 시작하기 전에

시작 정점에서 각각의 정점까지의 거리를 나타내는 dist 배열과

PriorityQueue인 pq를 초기화한다.

이때 (정점, 시작정점부터 해당 정점까지의 거리)인 객체를 사용한다.

여기서 우선순위 큐를 사용한다는 것이 중요한데

이 블로그를 보면 자세하게 정리되어 있다.

 

첫 번째로 pq에서 poll()을 하는데 이때 pq의 조건은 해당 정점까지의 거리가

작은애 들을 우선적으로 poll 하게 Comparator나 Comparable을 구현해야 한다.

처음 들어있던 (1,0)을 꺼내서

list.get(1)을 통해 1번 정점과 연결되어 있는 2번, 3번 정점에 대해 

1번 정점에서부터 해당 정점들까지의 거리를 보고

이전에 dist[2], dist[3]에 저장되어 있던 값들과

비교해서 더 작은 값을 골라 dist[] 배열에 업데이트해준다.

그리고 더 작을 경우에만 pq에 해당 정점과 해당 정점까지의 새로운 거리를 add 해준다.

 

마찬가지 작업을 반복해 준다.

 

위와 같이 만약 기존에 저장되어 있던 값보다 새로 구한 값이 더 작다면

해당 값을 dist[] 배열에 꼭 업데이트해줘야 한다.

 

이렇게 dist배열의 모든 값이 채워졌다. 해당 값들의 의미는 시작정점인 1로부터

각각의 정점까지의 최소 거리를 나타낸 것이다.

이제 문제의 조건에 맞게 각각의 정점까지의 거리를 출력해 주면 된다.

pq를 보면 하나 남은 객체가 있다. 처음부터 들어갔지만

pq의 조건에 따라 마지막까지 남은 객체이다.

이렇게 의미 없는 객체들을 거르기 위해

while() 문에 초반부에 조건을 걸어 거를 수 있다.

 

package boj;

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

public class BOJ1753 {
    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 K = Integer.parseInt(br.readLine()); // 시작 정점
        int[] dist = new int[V+1]; // 정점까지의 거리
        PriorityQueue<Node> pq = new PriorityQueue<>((o1,o2) -> o1.cost - o2.cost);
        int MAX = Integer.MAX_VALUE;
        for(int i = 0; i < dist.length; i++){
            dist[i] = MAX;
        }
        dist[K] = 0;

        List<List<Node>> list = new ArrayList<>();
        for(int i = 0; i < V+1; i++){
            list.add(new ArrayList<>());
        }

        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.get(u).add(new Node(v, w));
        }

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

        while(!pq.isEmpty()){
            Node now = pq.poll();

            if(dist[now.vertex] < now.cost) continue;

            for(Node next: list.get(now.vertex)){
                int newCost = dist[now.vertex] + next.cost;

                if(dist[next.vertex] > newCost){
                    dist[next.vertex] = newCost;
                    pq.add(new Node(next.vertex, newCost));
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 1; i < dist.length; i++){
            sb.append(dist[i] == MAX ? "INF" : dist[i]).append("\n");
        }

        System.out.println(sb);


    }
    static class Node{
        int vertex;
        int cost;

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