백준 1753 자바 최단거리 다익스트라 알고리즘 시간복잡도 JAVA

 

 

백준 1753 최단거리 문제는 다익스트라 알고리즘을 사용해서 풀어보는 문제다. 우선순위 큐를 사용해야 하고, 인접한 그래프의 방향성이 존재하는 그래프의 정보가 입력값으로 주어진다. 최단거리를 구하는 방법으로 우선순위 큐를 사용해서 문제를 풀어본다.

 

다익스트라 알고리즘이란?

양수의 그래프 한 정점에서 주변 정점까지 도달하는 최단거리를 구하는 알고리즘이다. 초기 모델은 우선순위 큐를 사용하지 않아 O(V^2)였다.  이 후 최소 우선 큐가 도입되면서 피보나치 힙으로 수행되는 시간복잡도는 O(|E| + |V|log|V|)가 된다. 다익스트라 알고리즘은 음이 아닌 가중치를 가지는 무작위유향 그래프에서 단일 소스 최단 경로 알고리즘 중에서 가장 빠른 알고리즘으로 알려져 있다. 

 

다익스트라 알고리즘

 

1. 모든 정점을 미방문 상태로 표시한다.
2. 모든 정점에 거리값을 부여한다.
3. 현재 정점에서 미방문 주변 정점의 거리를 현재 정점에서 계산한다. 현재 정점 A의 거리가 6이고 주변 정점 B까지 거리가 2라면 A->B의 거리는 6+2=8이 된다. 만약 이전의 B로의 거리가 8보다 크다면 8로 변경한다.
4. 모든 주변노드 검색이 완료 되었다면 큐에서 제거하고 새롭게 추가된 큐 요소를 추출해서 검색을 이어나간다.
5. 도착정점이 방문 표시가 된다면 알고리즘은 종료된다.

 

백준 1753 최단 거리 문제에 입력값으로 주어진 그래프의 정보를 시각적으로 표시하면 아래 그림이 된다. 방향성이 있는 그래프이기 때문에 정점(1)과 정점(5)간의 우선순위는 1이지만 정점(1)에서 정점(5)로 가는 방법은 없으므로 "INF"가 출력되는 것이다.

백준 1753 최단 거리 자바 알고리즘

 

 

 

백준 1753 최단 거리 자바 알고리즘

백준 1753 최단 거리 자바 알고리즘

 

 

 

백준 1753 최단 거리 자바 알고리즘 JAVA CODE

/*
    Owner : Developer Blog
    Title : 최단경로
    Algorithm : 다익스트라 알고리즘
    Date : 2022-03-24
*/


import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;

public class A_1753 {
    
    // 정점의 정보를 담고 있는 Node class 선언
    static class Node{
        int idx, cost; // 정점의 번호와 우선순위(비용)를 저장한다.

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

    }

    public static int V,E,K; // 정점, 간선의 갯수와 시작점 K
    public static ArrayList<ArrayList<Node>> graph; // 2원 배열 선언 
    public static int[] dist; // 정점간 이동횟수 카운트


    public static void main(String[] args){

        Scanner in = new Scanner(System.in);

        V = in.nextInt();
        E = in.nextInt();
        K = in.nextInt();

        // 그래프 초기화 진행
        graph = new ArrayList<ArrayList<Node>>();

        // 정점의 갯수 만큼 그래프의 노드들을 초기화 한다.
        for(int i=0; i<V+1; i++){
            graph.add(new ArrayList<Node>());
        }

        // 정점의 번호와 우선순위를 담은 Node Instance들을 2차원 그래프 배열에 삽입한다.
        for(int i=0; i<E; i++){
            int u = in.nextInt();
            int v = in.nextInt();
            int w= in.nextInt();

            graph.get(u).add(new Node(v, w));
        }
        
        // 정점 카운터 초기화
        dist = new int[V+1];

        // 정점 카운터를 4byte MAX값으로 초기화 진행
        for(int i=0; i<V+1; i++){
            dist[i] = Integer.MAX_VALUE;
        }

        // 최소비용을 기준으로 다익스트라 알고리즘을 구성한다. 
        PriorityQueue<Node> queue = new PriorityQueue<Node>((o1, o2) -> Integer.compare(o1.cost, o2.cost));
        // 시작 정점에서 가장 짧은 정점은 시작 정점이다.
        queue.offer(new Node(K, 0));
        // 처음에는 시작 정점이 선택되므로 시작 정점에 0을 삽입한다.
        dist[K] = 0;

        // 우선순위 큐를 while 문으로 순회한다.
        while(!queue.isEmpty()){
            // 큐에서 요소를 추출한다.
            Node temp = queue.poll();

            // 해당 새로운 정점의 카운터가 새로운 정점의 우선순위보다 작다면 순회를 뛰어넘는다.
            if(dist[temp.idx] < temp.cost){
                continue;
            }

            // 선택된 정점의 주변 정점을 검색한다.
            for(int i=0; i<graph.get(temp.idx).size(); i++){
                Node nextNode = graph.get(temp.idx).get(i);
                // 주변 정점의 정점 카운터와 현재 정점의 우선순위+주변 정점의 우선순위를 비교해서 더 작은 값을 선택한다.
                if(dist[nextNode.idx] > temp.cost + nextNode.cost){
                    dist[nextNode.idx] = temp.cost+nextNode.cost;
                    queue.offer(new Node(nextNode.idx, dist[nextNode.idx]));
                }
            }
        }

        // 정점 카운터를 순회하면서 각 정점에 도달하기 까지 걸린 거리를 출력한다.
        for(int i=1; i<V+1; i++){
            if(dist[i] == Integer.MAX_VALUE){
                System.out.println("INF");
            }
            else{
                System.out.println(dist[i]);
            }
        }
        
    }
}

 

 

백준 1753 최단 거리 자바 알고리즘 제출 결과