[JAVA] 백준 1753 다익스트라

 

 

 

 

 

1753번: 최단경로

문제

방향그래프가 주어졌을 때 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오.

풀이

하나의 출발점에서 다른 모든 노드로 향하는 최단 거리를 구하라는 문제이기 때문에 다익스트라 알고리즘을 사용하여 풀었습니다.

📌 입력

        boolean[] V = new boolean[N];
        ArrayList<Node>[]A = new ArrayList[N];
        int[] distance = new int[N];

        for(int i=1; i<N; i++){
            A[i] = new ArrayList<>();
            distance[i] = INF;
        }

        for(int i=0; i<E; i++){
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            A[a].add(new Node(b, w));
        }

    static class Node{
        int dest;
        int weight;
        Node(int dest, int weight){
            this.dest=dest;
            this.weight = weight;
        }
    }

Node : 노드 클래스를 사용해서 목적지와 가중치를 저장했습니다.

A : 연결 리스트 형태의 그래프를 구현했습니다. (방향 그래프이기 때문에 A → B일때, A에만 저장)

distance : 현재 최단 거리 배열

📌 다익스트라 알고리즘

먼저 기본적인 다익스트라 알고리즘은 다음과 같습니다.

1. 현재 distance 중에서 가장 짧은 거리를 가지는 정점을 선택한다.
2. 해당 정점에 연결된 간선을 토대로 갱신한다. (현재 distance > 선택된 정점까지의 거리 + 선택된 정점에서 다음 정점까지의 거리)
3. 모든 정점을 방문(연결되어 있지 않은 정점 제외)한다. (반복)

이해하기 쉽게 기본적인 다익스트라 알고리즘을 토대로 먼저 설명하겠습니다.

1. 현재 distance 중에서 가장 짧은 거리를 가지는 정점을 선택

            for(int j=1; j<N; j++){
                if(!V[j] && distance[min] > distance[j]){
                    min = j;
                }
            }
            if(min == 0) break;

방문한 적이 없고 가장 최소 거리를 가지는 인덱스를 가져옵니다.

만약 min이 초기화된 값과 일치하면 연결된 모든 정점을 방문했다는 의미이므로 프로그램을 종료합니다. (연결되지 않은 정점이 존재할 수 있기 때문이다.)

2. 해당 정점에 연결된 간선을 토대로 갱신한다.

            // 해당 노드를 기준으로 distance를 갱신한다.
            for(Node x : A[min]){
                distance[x.dest] = Math.min(distance[x.dest], distance[min] + x.weight);
            }

min인덱스로 선택된 정점과 연결된 정점들을 distance 배열에 갱신합니다.

min 정점과 연결된 정점까지의 거리가 “distance 배열에 있는 정점 > min 까지의 거리 + min에서 연결된 정점까지의 거리” 둘 중에서 작은 값을 distance 배열에 갱신합니다.

📌 기본 다익스트라 알고리즘

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    static final int INF = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken())+1;
        int E = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(br.readLine());

        boolean[] V = new boolean[N];
        ArrayList<Node>[]A = new ArrayList[N];
        int[] distance = new int[N];

        for(int i=1; i<N; i++){
            A[i] = new ArrayList<>();
            distance[i] = INF;
        }

        for(int i=0; i<E; i++){
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            A[a].add(new Node(b, w));
        }

        distance[0] = INF;
        V[S] = true;
        distance[S] = 0;
        for(Node x : A[S]){
            distance[x.dest] = Math.min(distance[x.dest], x.weight);
        }

        for(int i=2; i<N; i++){
            // 거리가 가장 짧은 노드를 선택한다.
            int min = 0;
            for(int j=1; j<N; j++){
                if(!V[j] && distance[min] > distance[j]){
                    min = j;
                }
            }
            if(min == 0) break;
            V[min] = true;
            // 해당 노드를 기준으로 distance를 갱신한다.
            for(Node x : A[min]){
                distance[x.dest] = Math.min(distance[x.dest], distance[min] + x.weight);
            }
        }

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

        System.out.println(sb);

    }
    static class Node{
        int dest;
        int weight;
        Node(int dest, int weight){
            this.dest=dest;
            this.weight = weight;
        }
    }
}

여기까지가 기본적인 다익스트라 알고리즘을 방법입니다.

하지만 이 방법은 반복마다 모든 distance를 돌면서 최소값을 찾아야하기 때문에 시간이 오래걸렸습니다.

자바에서는 우선순위 큐를 사용하여 최적화한 다익스트라 알고리즘을 사용할 수 있습니다.

1. 현재 distance 중에서 가장 짧은 거리를 가지는 정점 선택

        q.add(new Node(S, 0));
        distance[S] = 0;
        while (!q.isEmpty()){
            Node now = q.poll();

우선순위 큐를 사용하기 때문에 우선순위에서 꺼낸 정점이 가장 짧은 거리를 가지는 정점이 됩니다. (Node의 weight로 정렬)

2. 해당 정점에 연결된 간선을 토대로 갱신한다.

            if(V[now.dest]) continue;
            V[now.dest] = true;
            for (Node x : A[now.dest]){
                if(distance[x.dest] > distance[now.dest] + x.weight) {
                    distance[x.dest] = distance[now.dest] + x.weight;
                    q.add(new Node(x.dest, distance[x.dest]));
                }
            }
        }

문제에서 서로 다른 정점 사이에 여러개의 간선을 가질 수 있다고 했기 때문에 V를 두어서 방문한 노드는 다시 방문하면 안됩니다.

현재 정점과 연결된 정점들을 돌면서 distance를 갱신하고 큐에 해당 정점을 갱신된 거리로 담아줍니다.

📌 최적화된 다익스트라 알고리즘

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    static final int INF = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken())+1;
        int E = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(br.readLine());

        PriorityQueue<Node> q = new PriorityQueue<>((o1, o2) -> {
            return o1.weight - o2.weight;
        });
        boolean[] V = new boolean[N];
        ArrayList<Node>[]A = new ArrayList[N];
        int[] distance = new int[N];

        for(int i=1; i<N; i++){
            A[i] = new ArrayList<>();
            distance[i] = INF;
        }

        for(int i=0; i<E; i++){
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            A[a].add(new Node(b, w));
        }

        q.add(new Node(S, 0));
        distance[S] = 0;
        while (!q.isEmpty()){
            Node now = q.poll();
            if(V[now.dest]) continue;
            V[now.dest] = true;
            for (Node x : A[now.dest]){
                if(distance[x.dest] > distance[now.dest] + x.weight) {
                    distance[x.dest] = distance[now.dest] + x.weight;
                    q.add(new Node(x.dest, distance[x.dest]));
                }
            }
        }

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

        System.out.println(sb);

    }
    static class Node{
        int dest;
        int weight;
        Node(int dest, int weight){
            this.dest=dest;
            this.weight = weight;
        }
    }
}

결과

기본적인 다익스트라 알고리즘

최적화된 다익스트라 알고리즘

시간차이가 많이 나는 것을 볼 수 있었습니다.