[백준 1753 : JAVA] 최단경로 / 다익스트라

개요

 

이 문제는 가중치가 1이 아니고 음의 가중치도 아니기 때문에 다익스트라를 이용하여 풀이할 수 있다.

다익스트라는 음의 가중치를 가지는 경우 사용할 수 없다.

다익스트라를 구현할 때 인접 행렬, 인접 리스트 둘 다 구현할 수 있는데 리스트가 효율적인 경우가 많기 때문에 인접 리스트로 구현하였다.

 

문제

 

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

 

입력

 

풀이

 

다익스트라는 한 노드에서 모든 노드로 가는 최단거리를 구할 수 있다.

이때 최단거리를 저장하는 배열 + 우선순위 큐를 이용하여 구현할 수 있다.

위의 입력 값을 그래프로 표현하면 다음과 같다.

 

아래의 표는 최단거리를 저장하는 배열에 값들을 나타낸 표이다.

 

0. 모든 값들이 무한대로 저장되어 있다.

 

1. 시작지점인 1을 0으로 저장하고 1에서 갈 수 있는 노드들의 값들을 변경시켜준다.

 

2. dist배열에서 (아직 검사하지 않고 & 최솟값)을 기준으로 갈 수 있는 노드들의 값들을 변경시켜준다.

    이때 dist[2] + (2에서 i까지의 가중치)< dist[i] 인 경우만 갱신해준다.

    dist[2] + 5 < dist[4] (INF) 이기 때문에 갱신해준다.

 

3. dist[3] + (3에서 i까지의 가중치)< dist[i] 를 만족하는 게 없기 때문에 갱신하지 않는다.

 

4. dist[4] + (4에서 i까지의 가중치)< dist[i] 를 만족하는 게 없기 때문에 갱신하지 않는다.

 

위에 표를 코드로 구현할 때 dist배열 중 최솟값을 가지는 노드를 구하기 위해 우선순위 큐를 이용한다.

 

코드

 

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

class Node implements Comparable<Node>{
    int end, weight;

    public Node(int end, int weight){
        this.end = end;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node o) {
        return weight - o.weight;
    }
}

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private static final int INF = 100_000_000;
    static int v,e,k;
    static List<Node>[] list;
    static int[] dist;


    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        v = Integer.parseInt(st.nextToken());
        e = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(br.readLine());
        list = new ArrayList[v + 1];
        dist = new int[v + 1];

        Arrays.fill(dist, INF);

        for(int i = 1; i <= v; i++){
            list[i] = new ArrayList<>();
        }
        // 리스트에 그래프 정보를 초기화
        for(int i = 0 ; i < e; i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            // start에서 end로 가는 weight 가중치
            list[start].add(new Node(end, weight));
        }

        StringBuilder sb = new StringBuilder();
        // 다익스트라 알고리즘
        dijkstra(k);
        // 출력 부분
        for(int i = 1; i <= v; i++){
            if(dist[i] == INF) sb.append("INF\n");
            else sb.append(dist[i] + "\n");
        }

        bw.write(sb.toString());
        bw.close();
        br.close();
    }

    private static void dijkstra(int start){
       PriorityQueue<Node> queue = new PriorityQueue<>();
       boolean[] check = new boolean[v + 1];
       queue.add(new Node(start, 0));
       dist[start] = 0;

       while(!queue.isEmpty()){
           Node curNode = queue.poll();
           int cur = curNode.end;

           if(check[cur] == true) continue;
           check[cur] = true;

           for(Node node : list[cur]){
               if(dist[node.end] > dist[cur] + node.weight){
                   dist[node.end] = dist[cur] + node.weight;
                   queue.add(new Node(node.end, dist[node.end]));
               }
           }
       }
    }
}