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

문제 보러가기

1916번: 최소비용 구하기

[코드]

 

import java.io.*; import java.util.*; class Main {     static List<List<int[]>> lists; //트리 정보를 담는다.     static int[] dijkstra; //최소 거리를 저장할 배열     public static void main(String[] args) throws IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));         StringTokenizer st;         int N = Integer.parseInt(br.readLine());         int M = Integer.parseInt(br.readLine());         dijkstra = new int[N + 1];         Arrays.fill(dijkstra, Integer.MAX_VALUE); //모든 거리를 최대값으로 저장한다. 100,000보다 크다면 무슨 값이든 상관없다.         lists = new ArrayList<>();         for (int i = 0; i <= N; i++) lists.add(new ArrayList<>()); // 트리 정보를 담기위해서 리스트를 초기화한다.         for (int i = 0; i < M; i++) {             st = new StringTokenizer(br.readLine());             int A = Integer.parseInt(st.nextToken());             int B = Integer.parseInt(st.nextToken());             int value = Integer.parseInt(st.nextToken());             lists.get(A).add(new int[]{B, value}); //단방향이기 때문에 A에서 B로 향할때 비용만을 저장한다.         }         st = new StringTokenizer(br.readLine());         int start = Integer.parseInt(st.nextToken()); // 시작점         int end = Integer.parseInt(st.nextToken()); // 목표지점         dik(start);         bw.write(dijkstra[end] + "");         bw.close();     }     public static void dik(int start) {         // 비용을 오름차순으로 우선순위큐에 저장한다.         PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));         // 시작점과 시작점에서 비용을 넣는다. 시작점에서 시작점은 비용이 0이다.         queue.add(new int[]{start, 0});         // 방문처리를 위한 boolean배열         boolean[] visited = new boolean[lists.size()];         // 시작점은 0이다!         dijkstra[start] = 0;         /*         전형적인 다익스트라 알고리즘이다.         이미 방문한 노드라면 다음 노드로 넘어간다.         현재 방문중인 노드와 다음 노드로 향하는 비용을 더한 값이         기존에 배열에 저장되어있는 비용보다 작다면 갱신하고         그 비용과 다음 노드로 향하는 비용을 우선순위큐에 넣어준다.          */         while (!queue.isEmpty()) {             int[] node = queue.poll();             if (visited[node[0]]) continue;             visited[node[0]] = true;             for (int[] goals : lists.get(node[0])) {                 if (dijkstra[node[0]] + goals[1] < dijkstra[goals[0]]) {                     dijkstra[goals[0]] = dijkstra[node[0]] + goals[1];                     queue.add(new int[]{goals[0], dijkstra[goals[0]]});                 }             }         }     } }

[알고리즘]

1. 시작점에서 각 노드로 향하는 최소거리를 저장할 배열에 100,001보다 큰 수로 채운다.

2. 트리 정보를 저장할 리스트를 만든다.

3. 다익스트라 알고리즘

    3-1. 노드 간의 비용을 기준으로 오름차순 우선순위큐를 생성한다.

    3-2. 시작점과 시작점의 비용(0)을 우선순위큐에 넣는다.

    3-3. 출발노드의 비용과 목적지노드로 향하는 비용이 기존의 목적지노드로 향하는 비용보다 작다면

(100,001보다 큰수로 배열을 채운 이유) 기존의 배열을 갱신하고 우선순위큐에 목적지노드를 출발점과 비용을 넣어준다.

    3-4. 3-1 ~ 3-3 과정을 모든 노드를 돌 때까지 반복한다. 여기서 방문 노드를 방문처리 한다.

4. 다익스트라 알고리즘으로 생성된 배열에서 목적지 노드 값을 결과로 출력한다.