자바(백준) 1916 최소비용 구하기

오답 노트 & 새로 알게 된 점

해당 문제도 전에 풀었던 최단경로와 유사한(?) 거의 비슷한 문제이다.

다익스트라 알고리즘을 제대로 알고 있다면 쉽게 풀 수 있다.

 

---

2021.12.27 재풀이

다익스트라를 짜면서 TLE, MLE를 다 보았다.

 

1번을 if절이라 하고, 2번을 =을 안붙일 때라고 말하겠다.

 

처음 코드에는 1번과 2번 모두 없었다.

그래서 제출을 하면 TLE가 났다.

 

1번 코드를 작성한 뒤 제출하면 이제 MLE가 난다.

 

그래서 2번 코드를 작성하고 나니까 AC를 받았다.

 

다익스트라를 하면서 최적화?라고 해야하나 이게 필요한 것 같다.

 

앞으로 다익스트라를 풀면서 1번과 2번의 조건은 절대 까먹지 말아야겠다.

 

---

 

코드

package Graph;
 
import java.io.*;
import java.util.*;
 
public class BOJ1916 {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int nV, nE;
    static ArrayList<Node> node[];
    static int dist[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        nV = atoi(br.readLine());
        nE = atoi(br.readLine());
 
        node = new ArrayList[nV + 1];
        dist = new int[nV + 1];
 
        for (int i = 0; i <= nV; i++) {
            node[i] = new ArrayList<>();
        }
 
        for (int i = 0; i < nE; i++) {
            st = new StringTokenizer(br.readLine());
            int from = atoi(st.nextToken());
            int to = atoi(st.nextToken());
            int wei = atoi(st.nextToken());
 
            node[from].add(new Node(to, wei));
        }
 
        st = new StringTokenizer(br.readLine());
        int start = atoi(st.nextToken());
        int end = atoi(st.nextToken());
 
        dijkstra(start);
 
        System.out.println(dist[end]);
    }
 
    static void dijkstra(int start) {
        for (int i = 1; i <= nV; i++) dist[i] = Integer.MAX_VALUE;
 
        PriorityQueue<Info> pq = new PriorityQueue<>((o1, o2) -> {
            return o1.dist - o2.dist;
        });
 
        pq.offer(new Info(start, 0));
        dist[start] = 0;
 
        while (!pq.isEmpty()) {
            Info info = pq.poll(); //info에는 현재 정점이 저장
 
            if(dist[info.idx] != info.dist) continue;
 
            for (Node n : node[info.idx]) {
                if(dist[n.to] <= dist[info.idx] + n.wei) continue; //n.to는 연결된곳
 
                dist[n.to] = dist[info.idx] + n.wei;
                pq.offer(new Info(n.to, dist[n.to]));
            }
        }
    }
    static class Info{
        int idx, dist;
 
        public Info(int idx, int dist) {
            this.idx = idx;
            this.dist = dist;
        }
    }
    static class Node{
        int to, wei;
 
        public Node(int to, int wei) {
            this.to = to;
            this.wei = wei;
        }
    }
}