<Algorithm> 50. 1916번 최소비용 구하기(Dijkstra)

1. 1916번 최소비용 구하기(Dijkstra)

• 다익스트라 알고리즘 문제, for문을 이용하는 방법과 우선순위 큐를 이용하는 방법이 있는데 우선순위 큐를 사용하는 것이 좋다.
• 다익스트라는 시작정점에서 인접정점의 가중치가 가장 최소가 되는 선택하는 그리디 알고리즘이다.
• 시작정점 -> 인접정점들의 정보 -> 최저비용 정점으로 이동 -> 인접정점들의 정보 -> 업데이트(경유할 때 더 최소비용일 경우)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Comparator; import java.util.PriorityQueue; import java.util.StringTokenizer; public class Main {       static int[] dist;     static int[] path;     static boolean[] visited;     public static void main(String[] args) throws IOException {         BufferedReader br =new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st;         int N = Integer.parseInt(br.readLine())+1;         int M = Integer.parseInt(br.readLine());                  ArrayList<Edge>[] aLists = new ArrayList[N];                  dist = new int[N];         path = new int[N];         visited = new boolean[N];                  for(int i = 0; i < N; i++) {             dist[i] = Integer.MAX_VALUE;             path[i] = -1;             aLists[i] = 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 w = Integer.parseInt(st.nextToken());             aLists[a].add(new Edge(b, w));         }         st = new StringTokenizer(br.readLine());         int a = Integer.parseInt(st.nextToken());         int b = Integer.parseInt(st.nextToken());                  dijkstra(a, aLists);         System.out.println(dist[b]);     }          public static void dijkstra(int startVertex, ArrayList<Edge>[] aLists) {                           PriorityQueue<Edge> pq = new PriorityQueue<>(new Comparator<Edge>() {             @Override             public int compare(Edge o1, Edge o2) {                 return o1.weigth - o2.weigth;             }         });                       dist[startVertex] = 0; // 시작정점         path[startVertex] = 0; // 시작점                  pq.add(new Edge(startVertex, dist[startVertex]));         // 시작 위치 큐에 저장                  while(!pq.isEmpty()) {             Edge e = pq.poll();              int vertex = e.vertex;             // 방문 정점                          if(visited[vertex]) continue;                          visited[vertex] = true;                                       for(Edge edge : aLists[vertex]) {                 //방문정점의 인접정점들 확인                                      int destination = edge.vertex;                     // 인접정점                                           int weigth = edge.weigth;                     // 인접정정의 가중치                                          if(dist[destination] > dist[vertex] + weigth ) {                     // 경유할 경우와 직진할 경우의 가중치 비교, 경유할 경우가 더 가중치가 덜 하다면                         dist[destination] = dist[vertex] + weigth;                         // 목적지 가중치 변경 ( 시작 정점부터 현재까지의 가중치 )                          path[vertex] = destination;                         // 루트 경유(목적)지 저장                         pq.add(new Edge(destination, dist[destination]));                         // 큐에 저장, 시작정점부터 해당 정점까지의 가중치 등록                     }                 }         }              } }     class Edge{     int vertex,weigth;       public Edge(int adj, int weigth) {         super();         this.vertex = adj;         this.weigth = weigth;     }      } Colored by Color Scripter

cs