백준 : 1916

https://www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

 

package com.ssafy.Backjoon;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class B1916 {
    static int N;
    static int M;
 
    public static class Bus implements Comparable<Bus>{
        int v;
        int w;
 
        public Bus(int v, int w) {
            super();
 
            this.v = v;
            this.w = w;
        }
        public Bus(int v) {
            this.v = v;
        }
        @Override
        public int compareTo(Bus o) {
            if(this.w>o.w) {
                return 1;
            }
            else {
                return-1;
            }
        }
 
    }
 
    static ArrayList<Bus> list[];
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        
        list = new ArrayList[N+1];
        for(int n=1;n<=N;n++) {
            list[n] = new ArrayList<Bus>();
        }
        
        
        for(int m=0;m<M;m++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            list[u].add(new Bus(v,w));
        }
        
        // 출발지 도착지
        st = new StringTokenizer(br.readLine());
        int u = Integer.parseInt(st.nextToken());
        int v = Integer.parseInt(st.nextToken());
        
        System.out.println(Dijckstra(u, v));
        
    }
 
    public static int Dijckstra(int u, int v) {
        int digit[] = new int[N + 1];
        boolean check[] = new boolean[N + 1];
 
        Arrays.fill(digit, Integer.MAX_VALUE);
 
        PriorityQueue<Bus> q = new PriorityQueue<>();
        // 시작점은 비용이 없다 ㅎㅎㅎ
        digit[u] = 0;
        q.add(new Bus(u));
 
        while (!q.isEmpty()) {
            Bus b = q.poll();
 
            // 방문한 노드는 스킵한다.
            if (check[b.v])
                continue;
            check[b.v] = true;
            int len = list[b.v].size();
            
            for (int i = 0; i < len; i++) {
 
                if (digit[list[b.v].get(i).v] > digit[b.v] + list[b.v].get(i).w) {
                    digit[list[b.v].get(i).v] =  digit[b.v] + list[b.v].get(i).w;
                    q.add(new Bus(list[b.v].get(i).v,digit[b.v] + list[b.v].get(i).w));
                }
    
                
            }
 
        }
 
        return digit[v];
    }
 
}
 

 

 

다잌스트라 연습

1. 시작노드 u 도착노드 v 라고할 대

digit 을 INF 값으로 초기화 한다.

시작노드의 digit[u] = 0 으로 초기화하고 우선순위큐에 넣는다.

 

이때 우선순위 큐의 정렬순서를 digit값으로 한다면 항상 digit값이 최소인것을 먼저 가져올 수가 있다.

항상 최소인 비용의 노드에서 탐색하는 것이 가장 적은 비용을 얻을 수 있다.

 

또한 현재노드에서 다른노드에 digit값을 바꿧을대 그노드를 Q에 추가한다.

 

방문한 노드는 탐색하지 않는다 되어있지만 사실상 저소스는 없어도 우선순위 큐에서 정리된다.

 

만약 우선순위 큐가아니라 일반 큐를 사용하고 check를 사용한다면 당연히 에러가난다.

 

이때는 일반큐에서는 check를 사용하지않고 q가 사라질때까지 사용한다.

 

우선순위 큐를 쓰면 항상 최적의 값으로한다.