[알고리즘] 다익스트라 알고리즘, 백준 1753번 프로그래머스 배달

다익스트라 알고리즘의 개념

---

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

하나의 정점에서 모든 정점으로의 최단 경로를 계산하는 것을 목표로 하는 알고리즘
Single source shortest paths problem

 

로직

1. 모든 정점들은 처음에 무한대 값을 갖는다. 
2. 정점 A에서 정점 B가 이어지면 정점 A까지의 최단거리 + A에서 B까지의 거리를 계산한다.
3. 만약 B가 가지고 있는 값(즉, A에서 B로 이어지는 다른 경로에 의한 값)과 2번에서 계산한 값과 비교하여 후자가 더 작다면 갱신한다.
4. 가장 작은 값을 가지고 있는 정점부터 이어서 반복한다. (가장 작은 값을 가지고 있는 정점부터 시작하는 이유는 작지 않은 값부터 시작되면 쓸모없는 연산이 진행되기 때문이며, 올바른 결과를 얻어낼 수 없다.)  

작은 값으로 갱신이 되어야 하는데, 큰 값을 가지고 있는 정점부터 시작되면 의미가 있을까? 없음.

 

다익스트라 알고리즘의 구현

---

구현 시 주의점 

• 우선순위 큐를 이용하여 가장 최소값을 가진 정점을 얻어내도록 한다.
• JAVA의 Priority Queue는 poll(), add()와 같이 추가,삭제 연산이 일어날 때 정렬을 수행한다.
• 우선순위 큐를 갱신할 때, 값이 바뀐 데이터만 다시 삽입하도록 한다. 
• 만약 인접 배열로 구현을 하게 되었을 때 공간 복잡도는 O(V^2)이며, 인접 리스트로 구현을 하게 되면 O(VE) 이다. 

 

구현 

• 백준 1753번 최단 경로 문제 https://www.acmicpc.net/problem/1753

public class ShortestPath {
    
    static Node[] nodes; 
    static List<List<int[]>> edge_weights;
    static boolean[] isChecked;
    static public final int INF = 1000000000;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int vertexCnt,edgeCnt; 
        
        String[] line = br.readLine().split(" "); 
        vertexCnt = Integer.parseInt(line[0]);
        edgeCnt = Integer.parseInt(line[1]);
        edge_weights = new ArrayList<>();
        nodes = new Node[vertexCnt+1];
        isChecked = new boolean[vertexCnt+1];
        
        // Node를 담고 있는 list를 초기화 한다.
        // 인접 리스트를 초기화 한다.
        edge_weights.add(new ArrayList<>());
        for(int cnt=1; cnt<=vertexCnt; cnt++) {
            nodes[cnt] = new Node(cnt);
            edge_weights.add(new ArrayList<>());
        }
        
        int startVertex = Integer.parseInt(br.readLine());
        nodes[startVertex].shortest_distance = 0;
        
        // 간선 가중치 리스트를 초기화 한다.
        for(int cnt=0; cnt<edgeCnt; cnt++) {
            line = br.readLine().split(" "); 
            int start = Integer.parseInt(line[0]);
            
            int[] end_weight = new int[2];
            end_weight[0] = Integer.parseInt(line[1]);
            end_weight[1] = Integer.parseInt(line[2]);
            
            edge_weights.get(start).add(end_weight);
        }
        
        // 최단 경로를 계산한다. 
        dijkstra(startVertex, vertexCnt);
        
        printNodes();
        
        line = null; 
        nodes = null;
        edge_weights = null;
    }
    
    private static void dijkstra(int startVertex, int vertexCnt) {
        PriorityQueue<Node> pqueue = new PriorityQueue<>();
        //모든 노드들을 우선순위 힙에 넣는다.
        for(int cnt=1; cnt<=vertexCnt; cnt++) {
            pqueue.add(nodes[cnt]);
        }
        
        //가장 경로 가중치가 작은 노드를 시작 노드로 선택한다.
        //만약 노드가 연결되어 있으면 해당 노드의 shortest path를 최신화 한다.
        //모든 노드가 시작 노드로 선택되었으면 종료한다.
        while(!pqueue.isEmpty()) {
            Node start = pqueue.poll();
            isChecked[start.num] = true;
            
            for(int[] list : edge_weights.get(start.num)) {
                int before = nodes[list[0]].shortest_distance;
                nodes[list[0]].shortest_distance = 
                        Math.min(nodes[list[0]].shortest_distance, start.shortest_distance + list[1]);  
                
                if(nodes[list[0]].shortest_distance != before) {
                    pqueue.remove(nodes[list[0]]);
                    pqueue.add(nodes[list[0]]);
                }
            }
        }
        pqueue = null;
    }
    
    private static void printNodes() {
        for(int idx=1; idx<nodes.length; idx++) {
            if(nodes[idx].shortest_distance == INF) {
                System.out.println("INF");
            }
            else 
                System.out.println(nodes[idx].shortest_distance);
        }
        System.out.println();
    }
    
    static class Node implements Comparable<Node> {
        int num;
        int shortest_distance;  
        
        public Node(int num) {
            this.num = num;
            this.shortest_distance = INF;
        }
 
        @Override
        public int compareTo(Node target) {
            if (this.shortest_distance < target.shortest_distance) {
                return -1;
            } else if (this.shortest_distance > target.shortest_distance) {
                return 1; 
            }
            return 0;
        }
        
        @Override
        public String toString() {
            return "[" + num + "," + shortest_distance + "]";
        }
    }
}
 
 

 

• 프로그래머스 배달 https://programmers.co.kr/learn/courses/30/lessons/12978

코딩테스트 연습 - 배달