[JAVA] 백준 1916 - 최소 비용 구하기

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

1916번: 최소비용 구하기

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


public class Main {

    public static int N;
    public static int V;
    public static ArrayList<Node>[] adjacentList;
    public static int[] table;
    public static HashSet<Integer> set = new HashSet<>();
    public static boolean[] visited;
    public static PriorityQueue<Node> queue = new PriorityQueue<>();

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        V = Integer.parseInt(br.readLine());
        table = new int[N + 1];
        Arrays.fill(table, Integer.MAX_VALUE);
        adjacentList = new ArrayList[N + 1];
        visited = new boolean[N + 1];
        for (int i = 0; i <= N; i++) {
            adjacentList[i] = new ArrayList<>();
        }
        for (int t = 0; t < V; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            adjacentList[u].add(new Node(v, w));
        }
        StringTokenizer st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());
        table[start] = 0;
        System.out.println(dijkstra(start, end));
    }

    public static int dijkstra(int start, int end) {

        queue.offer(new Node(start, 0));

        while (!queue.isEmpty()) {
            Node curNode = queue.poll();
            if(set.contains(curNode.num)){
               continue;
            }
            set.add(curNode.num);
            for (Node childNode : adjacentList[curNode.num]) {
                if (table[childNode.num] > table[curNode.num] + childNode.weight) {
                    table[childNode.num] = table[curNode.num] + childNode.weight;
                    queue.add(new Node(childNode.num, table[childNode.num]));

                }
            }


        }
        return table[end];
    }
}


class Node implements Comparable<Node> {
    int num;
    int weight;

    public Node(int num, int weight) {
        this.num = num;
        this.weight = weight;
    }

    public Node() {
    }

    @Override
    public String toString() {
        return "[" + num + ", " + weight + "]";


    }

    @Override
    public int compareTo(Node o) {
        return weight - o.weight;
    }

}

 

 

한노드를 방문했는지 확인하는 HashSet이 필요하다.

 

다익스트라 알고리즘상 O(V^2)이되게 로직을 구현해야한다.

로직을 조금 실수하면 space complexity나 time complexity를 초과하기때문에 조심해야한다.

특히 set을 언제추가하고 continue해야할지가 그 과정의 핵심이다.