BOJ#1916 최소비용 구하기

BOJ#1916 최소비용 구하기

* 문제

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

* 풀이

다익스트라 알고리즘을 이용합니다.

* 다익스트라 알고리즘 (Dijkstra algorithm)

1. 개요

 : 어떤 변도 음수 가중치를 갖지 않는 유향 그래프에서 주어진 출발점과 도착점 사이의 최단 경로 문제를 푸는 알고리즘이다. 

 : 다익스트라 알고리즘은 각각의 꼭짓점 v에 대해 s(시작점)에서 v까지의 최단 거리 d[v]를 저장하면서 작동한다. 알고리즘의 시작 시에 d[s]=0이고, s가 아닌 다른 모든 꼭짓점 v에 대해서는 d[v]=∞로 놓아 다른 꼭짓점에 대해서는 아직 최단 경로를 모른다는 사실을 표시한다. 알고리즘이 종료되었을 때 d[v]는 s에서 v까지의 최단 경로의 거리를 나타내게 되고, 만약 경로가 존재하지 않으면 거리는 여전히 무한대로 남는다.

 : 다익스트라 알고리즘은 변 경감(edge relaxation)이라고 불리는 기본 연산을 바탕으로 한다. s에서 u까지의 최단 경로(d[u])를 이미 알고 있고, u에서 v까지 길이가 w(u,v)인 변 (u, v)가 존재할 때, s에서 v까지의 최단 경로는 u까지의 최단 경로에 변 (u, v)를 추가함으로써 얻을 수 있다. 이 경로의 비용은 d[u]+w(u, v)가 되며, 이 비용이 현재의 d[v] 값보다 낮으면 d[v]를 새로운 값으로 바꾼다.

2. 실행 시간

 : 가장 간단한 구현으로, Q의 집합을 연결 리스트나 배열 구조로 구현하고 Extract-Min(Q) 함수를 단순한 선형 탐색으로 구현했을 때 실행 시간은 O(n^2) 시간이 된다.

만약 희소 그래프(sparse graph), 즉 n^2보다 훨씬 작은 개수의 변만을 갖는 그래프에 대해서는, 인접 리스트와 바이너리 힙 또는 피보나치 힙으로 구현한 우선순위 큐를 이용해 다익스트라 알고리즘을 더 효율적으로 구현할 수 있다. 이진 힙을 이용하면 실행 시간은 O((m+n)log n) 시간이 되고, 피보나치 힙을 통해 O((m+n)log n) 시간까지 개선할 수 있다.

3. 의사 코드

아래 알고리즘 의사코드에서 u := Extract_Min(Q)는 꼭짓점의 집합 Q에서 가장 작은 d[u]값을 찾은 다음 그 꼭짓점 u를 Q에서 제거한 후 반환하는 함수를 가리킨다.

 1   function Dijkstra(G, w, s)
 2      for each vertex v in V[G]                        // 초기화
 3            d[v] := infinity
 4            previous[v] := undefined
 5      d[s] := 0                                                     //덮어쓰기
 6      S := empty set
 7      Q := set of all vertices
 8      while Q is not an empty set                      // 알고리즘의 실행
 9            u := Extract_Min(Q)                                //집합 Q에서 d[u]가 최소인 u를 찾아 빼냄
10           S := S union {u}                                      //빼낸 u를 S에 삽입
11           for each v with edge (u,v) defined
12                  if d[v] > d[u] + w(u,v)
13                        d[v] := d[u] + w(u,v)              // 변(u,v)의 경감
14                        previous[v] := u                     //경로 추적할 때 쓰임//

만약 s에서 모든 v에 까지의 최소 경로를 찾는 것이 아니라, s에서 특정 꼭짓점 t까지의 최단 거리만을 알고 싶다면 8번째 행에 u != t의 조건을 추가하면 된다.

previous[]가 구해지면, 이를 이용해 다음과 같이 s에서 t까지의 최단 경로를 얻을 수 있다.

1 S := empty sequence
2 u := t
3 while defined u
4       insert u to the beginning of S
5       u := previous[u]

이제 S는 s에서 t까지의 최단 경로 위에 있는 꼭짓점들의 목록이 된다.

출처 :https://ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

- 1916번 문제 주의점

버스 비용을 입력 받을 때

즉, 노드 → 노드로 가는 간선(weight)를 입력 받을 때

중복되어 입력될 수 있음.

예) 아래와 같이 입력이 될 수 있으므로 1 → 2 간선의 비용은 최소값인 3으로 유지해야함.

1 2 3

1 2 5

1 2 7

+ 추천하는 다익스트라 기본 문제

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

---

* 나의 코드

https://github.com/stack07142/BOJ/tree/master/BOJ%231916_CalculateMinimumCost

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/*
 * BOJ#1916 최소비용 구하기
 * https://www.acmicpc.net/problem/1916
 */

public class Main {

   static final int INF = 1000000000;

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

      int n;
      int m;
      int[][] w;
      int[] d;
      boolean[] visited;
      int start, end;

      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

      n = Integer.parseInt(br.readLine());
      m = Integer.parseInt(br.readLine());

      w = new int[n + 1][n + 1];
      d = new int[n + 1];
      visited = new boolean[n + 1];

      for (int i = 0; i < n + 1; i++) {

         d[i] = INF;
         visited[i] = false;
         for (int j = 0; j < n + 1; j++) {
            w[i][j] = INF;

         }
      }
      for (int i = 0; i < m; i++) {

         int a, b;
         int weight;

         StringTokenizer st = new StringTokenizer(br.readLine());
         a = Integer.parseInt(st.nextToken());
         b = Integer.parseInt(st.nextToken());
         weight = Integer.parseInt(st.nextToken());

         //w[a][b] = weight;
         if (w[a][b] > weight) {
            
            w[a][b] = weight;
         }
      }

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

      dijkstra(start, n, m, w, d, visited);
      System.out.println(d[end]);

   }

   static void dijkstra(int start, int n, int m, int[][] w, int[] d, boolean[] visited) {

      int u;
      int dist;

      d[start] = 0;

      for (int i = 1; i < n + 1; i++) {

         dist = INF + 1;
         u = -1;

         for (int j = 1; j < n + 1; j++) {

            if (!visited[j] && d[j] < dist) {

               u = j;
               dist = d[j];
            }
         }

         for (int j = 1; j < n + 1; j++) {

            if (d[j] > d[u] + w[u][j]) {

               d[j] = d[u] + w[u][j];
            }
         }

         visited[u] = true;
      }
   }
}