알고리즘 지하철(C++)

2097 : 지하철

제한시간: 1Sec    메모리제한: 64mb
해결횟수: 623회    시도횟수: 2053회    Special Judge

지방에서 서울에 관광온 성수는 지하철 노선을 보고 깜짝 놀랐다. 노선이 엄청나게 복잡하기 때문이었다. 각 노선들이 서로 얽혀있어서 잘못하면 10분도 안걸리는 거리를 1시간 동안 갈 수도 있는 상황이었다.  어쩔 수 없이 성수는 현재 숙소에서 관광할 목적지까지 가장 짧은 시간에 도착할 수 있는 경로와 시간을 표로 만들려고 한다.

단, 각 지하철역에서 관광지가 있고, 지하철을 갈아타는데 소요되는 시간은 없다고 가정한다.

 

첫줄에 N(3≤N≤100), M(1≤M≤N)을 입력 받는다. N은 지하철역의 수, M은 원하는 목적역의 번호를 입력받는다.
둘째 줄부터 N개의 줄이 나오고, 각 줄에는 N개의 수 S가 입력된다. 
i번째 줄에서 j번째 수 Sij는 i번역에서 j번 역까지 가는데 걸리는 시간이다. 1번 역이 숙소가 있는 역이고, Sij에서 i = j 일 때는 항상 0 이다. (0≤S≤100)

목적 역까지 가는데 걸리는 최소 시간과 최소시간으로 가는 최단경로를 출력한다.

[Copy] 5 5 0 2 2 5 9 2 0 3 4 8 2 3 0 7 6 5 4 7 0 5 9 5 6 5 0

[Copy] 8 1 3 5

?

?

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 108 109 110 111 112 113 114 115 116 117 118 119

/**************************************************************     Problem: 2097     User: a132034     Language: C++     Result: Success     Time:3 ms     Memory:1740 kb ****************************************************************/     #include    <iostream> #include    <stack> using namespace std; #define X 0 #define O 1 #define MAX 99999 static int * visit;   int min(int*arr, int len) {     int min = MAX;     int res = -1;     for (int i = 0; i < len; ++i)     {         if (visit[i] == X)         {             if (arr[i] < min)             {                 min = arr[i];                 res = i;             }         }     }     return res; }   int main() {     int N, M;     int ** metro;     int * cost;     int * route;     stack<int> path;     int i;       cin >> N >> M;     metro = new int*[N];     cost = new int[N];     visit = new int[N];     route = new int[N];             for (int i = 0; i < N; ++i)     {         metro[i] = new int[N];         cost[i] = MAX;         visit[i] = X;     }     cost[0] = 0;       for (int i = 0; i < N; ++i)     {         for (int j = 0; j < N; ++j)         {             cin >> metro[i][j];         }     }       i = 0;     while (i != -1)     {         visit[i] = O;         for (int j = 0; j < N; ++j)         {             //각 시작점 i에서 갈 수 있는 곳의 cost를 계산하여 바꾸어 준다. (시작점으로부터 현재 점에 온 값 + 여기서 갈 수 있는 값)             //바뀌었을 경우 시작점 i에서 간 곳의 route를 저장한다.             if (i == j)                 continue;               if (cost[j] == MAX)             {                 cost[j] = metro[i][j];                 route[j] = i;             }             else             {                 if (cost[i] + metro[i][j] < cost[j])                 {                     cost[j] = cost[i] + metro[i][j];                     route[j] = i;                 }             }         }           //남은 위치 중 가장 코스트가 작으며 탐색하지 않은 위치에서 탐색         i = min(cost, N);     }       //최소값     cout << cost[M - 1] << endl;       //루트     int s = route[M - 1];     path.push(M);     path.push(route[M-1]+1);     do     {         s = route[s];         path.push(s + 1);     } while (s != 0);       while (!path.empty())     {         cout << path.top() << " ";         path.pop();     }       return 0; }

대표적인 다익스트라 알고리즘(Dijkstra's algorithm) 문제

다익스트라 알고리즘은 방향이 있는 가중치 그래프에서 출발점과 도착점사이의 최댄경로문제를 푸는 알고리즘. 

알고리즘은 생각보다 어렵지 않다. 

1. 시작점에서 시작한다. 

모든 점은 시작점에서 갈 수 없다면 cost가 없는 것( 코드에서는 MAX - 99999로 설정 ) , 방문한 점이라면 O, 아니라면 X ( 코드에서는 visit O,X로 설정

2. 시작점에서 갈 수 있는 모든곳의 cost를 계산한다. ( 코드에서는 cost 배열에 넣어줌 ) -> 이미 cost가 있는 경우 전의 값과 현재 값을 계산하여 작은 값을 넣어준다.

ex) 문제의 입력 예에서 

1 -> 5로 가는 기존의 루트의 cost는 9 

1 -> 3까지 가는 루트의 cost는 2 이고 3 -> 5까지 가는 루트의 cost는 6 이다. 2 + 6 = 8 

이럴 경우 기존의 값인 9를 대체하여 8을 해당 위치의 cost에 넣어준다. ( 코드에서는 cost[j] - 도착점 기준 - 에 저장)

3. 방문하지 않은 점(visit X) 중 가장 cost가 낮은 점을 찾는다. 

4. 2, 3을 방문하지 않은 점이 없을 때 까지 반복한다. 

cost[i]에 목표 i에 대한 최단거리가 저장된다. 

최단경로는 각 점의 위치의 이전 점의 위치를 저장한 후 스택을 이용해 가져오는 방법을 사용했다.