백준_ 최소비용구하기

다익스트라 알고리즘에 대해 자세히 설명된 곳을 추천한다.

http://www.playsw.or.kr/repo/cast/105

우선 위 주소로 가서 다익스트라 알고리즘이 어떻게 동작하는지 한번 살펴보길 추천한다. 단계별로 설명되어 있기 때문이 차근 차근 읽어보면 쉽게 이해할 수 있다.

내가 이해한 다익스트라 알고리즘은 출발지로부터 갈 수 있는 노드의 최단 거리를 모든 노드를 방문할 때까지 계속 갱하는 방법이다.

1. 먼저, 집에서 갈 수 있는 곳을 그림의 표에서 거리 칸에 써 넣는다.

2. 그리고 집에서 갈 수 있는 곳은 미용실, 슈퍼마켓, 영어학원 중에서 최단거리인 미용실로 간다.

3.다시 미용실에서 갈 수 있는 곳은 슈퍼마켓, 은행이다.(집은 이미 방문했으니 패스~)

여기서 슈퍼마켓으로 가는 경로는 집에서 바로 슈퍼마켓으로 가는 경로보다 짧다.

쉽게 말하면, 집->미용실->슈퍼마켓의 거리는 5+3=8인데 집->슈퍼마켓은 거리가 10이다.

그러니 그림의 표의 슈퍼마켓이 10에서 8로 값을 갱신하는 것이다.

이 부분이 다익스트라 알고리즘의 핵심인 것 같다. 알고리즘이 진행되면서 출발지인 집에서 갈 수 있는 노드들의 최단거리를 계속 갱신하는 것이다. 

모든 곳을 다 방문하면 알고리즘은 종료된다.

알고리즘의 의사코드는 나무위키에서 퍼왔다.

function Dijkstra(Graph, Source):
 
     dist[source] ← 0                           // 소스와 소스 사이의 거리 초기화 --출발지와 출발지의 거리는 당연히 0--
      prev[source] ← undefined              // 출발지 이전의 최적 경로 추적은 없으므로 Undefined

     create vertex set Q                       //노드들의 집합 Q(방문되지 않은 노드들의 집합) 생성 시작

      for each vertex v in Graph:           // Graph안에 있는 모든 노드들의 초기화
          if v ≠ source:                          // V 노드가 출발지가 아닐 경우(출발지를 제외한 모든 노드!)
            dist[v] ← INFINITY             // 소스와 V노드 사이에 알려지지 않은 거리 --얼마나 먼지 모르니까-- = 무한값 ( 모든 노드들을 초기화하는 값)
            prev[v] ← UNDEFINED       // V노드의  최적경로 추적 초기화
        add v to Q                            //  Graph에 존재하고 방금 전 초기화된 V 노드를 Q(방문되지 않은 노드들의 집합)에 추가

//요약하자면, Graph에 존재하는 모든 노드들을 초기화한 뒤, Q에 추가함.
      
      while Q is not empty:                      // Q 집합이 공집합 아닐 경우, 루프 안으로!
          u ← vertex in Q with min dist[u]    // 첫번째 반복에서는 dist[source]=0이 선택됨. 즉, u=source에서 시작
          remove u from Q                         // U 노드를 방문한 것이므로 Q집합에서 제거
          
          for each neighbor v of u:           // U의 이웃노드들과의 거리 측정
              alt ← dist[u] + length(u, v)      // 출발지 노드 부터 계산된 U노드까지의 거리 + V에서 U의 이웃노드까지의 거리
                                                             //= source to U + V to U = source to U
             if alt < dist[v]:               // 방금 V노드까지 계산한 거리(alt)가 이전에 V노드까지 계산된 거리(dist[v])보다 빠른 또는 가까운 경우
                 dist[v] ← alt            //  V에 기록된 소스부터 V까지의 최단거리를 방금 V노드까지 계산한 거리로 바꿈
                  prev[v] ← u            // 제일 가까운 노드는 지금 방문하고 있는 노드(U)로 바꿈
     return dist[], prev[] //계산된 거리값과 목적지를 리턴 

그리고 응용1도 없이 다익스트라 알고리즘을 푸는 문제이다. 출처는 백준에서 퍼왔다.

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

코드는 나무위키의 의사코드를 참고해서 C언어로 만들었다. 그래프를 인접행렬로 표현했다. 노드의 개수가 많아지면, STL의 vector를 이용하는게 편할 것 같다.

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

#include <stdio.h>   #define MAXNODE 1000 #define INFINIT 100000001   /* n : 노드의 개수, m : 버스 노선의 수 source : 출발지, destination : 목적지 adj[][] : 인접행렬 dist[] : 출발지로부터의 최소 비용 */ int n, m, source, destination; int adj[MAXNODE + 1][MAXNODE + 1]; long long dist[MAXNODE + 1];   void input() {     int from, to, w;     scanf("%d", &n);     scanf("%d", &m);       // 인접행렬을 모두 무한대 거리로 만든다.     for (int i = 1; i <= n; i++)         for (int j = 1; j <= n; j++)             adj[i][j] = INFINIT;       for (int i = 0; i < m; i++) {         scanf("%d %d %d", &from, &to, &w);                   // ** A->B로 가는 버스가 여러대일 수 있다.         if (adj[from][to] > w || adj[from][to] == 0)             adj[from][to] = w;     }     scanf("%d %d", &source, &destination); }   void dikstra() {     // Q : 방문지, 의사코드와 동일     int Q[MAXNODE + 1], Q_Size = n;       for (int v = 1; v <= n; v++)     {         dist[v] = INFINIT;         Q[v] = 0;;     }     dist[source] = 0;       while (Q_Size != 0)     {         int min_dst = INFINIT, u;         long long alt;           for (int v = 1; v <= n; v++)         {             if (Q[v] == 0 && dist[v] < min_dst)             {                 min_dst = dist[v];                 u = v;             }         }         Q[u] = 1;         Q_Size--;           for (int v = 1; v <= n; v++)         {             if (adj[u][v] == INFINIT) continue;                           alt = dist[u] + adj[u][v];             if (alt < dist[v])                 dist[v] = alt;         }     } }   int main() {     input();     dikstra();       printf("%lld\n", dist[destination]);     return 0; }