[Jungol] 정올 2097 지하철

출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1360&sca=4050

 Input 

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

 

 Output 

8

1 3 5

 

BFS 탐색할 때, 재방문 방지를 위해서 보통 visited[][] 배열을 두어서 재방문 여부를 확인합니다.

하지만 최단거리의 경우에는 재방문하더라도 더 나은 비용(cost)로 방문할 수 있습니다.

그렇기 때문에 vistied[][] 배열 값에 단순히 『0』, 『1』 로 방문 확인하지 않고

비용(cost)을 두어서 더 나은 경로인 경우 허용합니다.

 

※ 최단 거리의 경로

각 지점을 순회하면서 지금까지 온 경로를 누적할 수도 있지만 효율적이지 못합니다.

이때는 최소 비용으로 x 지점 바로 직전 지점을 path[]에 저장합니다.

    ex) path[x] = y = x지점에 도착하기 전에 y 지점에 도착

BFS 탐색이 끝나면 결과적으로 path[]에는 최소 비용으로 각 지점에 도달하기 위해 직전에 들리는 정점이 저장됩니다.

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define INF 2e9
const int LM = 102;
int N, M;
int map[102][102];
int visited[102];
int path[102];
int que[100 * 100];
int fr, re;
 
void input() {
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            scanf("%d", &map[i][j]);
        }
    }
}
 
int BFS() {
    for (int i = 1; i <= N; ++i) {
        visited[i] = INF;
    }
 
    que[re++] = 1;
    visited[1] = 0;
    
    while (fr < re) {
        int cur = que[fr++];
        for (int e = 2; e <= N; e++) {
            int cost = visited[cur] + map[cur][e];
            if (visited[e] <= cost) continue;
            que[re++] = e;
            visited[e] = cost;
            path[e] = cur;
        }
    }
 
    return visited[M];
}
 
void trace(int m) {
    if (m == 0) return;
    trace(path[m]);
    printf("%d ", m);
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    input();
    printf("%d\n", BFS());
    trace(M);
}