[Algorithm] 백준_최소비용 구하기_1916번 (JAVA) 다익스트라

📝문제

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

최소비용 구하기 1916번

티어: 골드 5

 

💡풀이

문제 유형

다익스트라

 

걸린 시간

60

 

시간 복잡도

O(M log N)

 

풀이 방법 도출

1. 문제에서 최소비용을 보고 무슨 알고리즘이더라...? 고민했던,, 문제 
2. 최근에 비슷한 문제를 풀었기 때문에 다익스트라 알고리즘을 생각보다 수월하게 구현할 수 있었따.
3. 이렇게 유형이 정해져있는 것은 비슷한 문제 여러개 풀다보면 감이 잡히는 거 같다.
4. 우선순위 큐를 사용하여 인접한 배열 리스트를 검사해 최소비용을 갱신해주었다
5. 처음 제출할때 시간초과가 나서 if(cost > dist[now]) continue; 이 조건을 추가해주었다.

import java.util.*;
import java.io.*;
class Main{
    static int INF = Integer.MAX_VALUE;
    static int[] dist;
    static int N;
    static ArrayList<Node>[] bus;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine()); //도시의 개수
        int M = Integer.parseInt(br.readLine()); //버스의 개수

        dist = new int[N+1];
        Arrays.fill(dist, INF);

        bus = new ArrayList[N+1];
        for(int i = 0; i <= N; i++){
            bus[i] = new ArrayList<>();
        }

        StringTokenizer st;
        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            bus[u].add(new Node(v, cost));
        }

        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        dist[start] = 0;
        dijkstra(start);

        System.out.println(dist[end]);
    }

    public static void dijkstra(int n){
        PriorityQueue<Node> pq = new PriorityQueue<>((a,b) -> a.cost);
        pq.add(new Node(n,0));
        boolean[] visited = new boolean[N+1];

        while(!pq.isEmpty()){
            Node current = pq.poll();
            int now = current.v;
            int cost = current.cost;
            
            if(cost > dist[now]) continue;

            for(Node node : bus[now]){
                int newCost = dist[now] + node.cost;
                if(newCost < dist[node.v]){
                    dist[node.v] = newCost;
                    pq.add(new Node(node.v, newCost));
                }
            }
        }

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

 

🤔Review

다익스트라..다익스트라..잊지말자 다익스트라