[SWEA] 1249. 보급로

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD

SW Expert Academy

 

풀이

 

* 다익스트라 알고리즘으로 최단 경로를 구한다. 

* 이 문제의 경우 "최단 경로"가 답이 되는 TC도 있지만, 조금 돌아가더라도 "복구 시간"이 가장 짧은 것을 정답으로 한다. 

* 그렇기 때문에 방문 표시를 단순히 좌표로 하면 안된다.

(조금 돌아갔을 때 복구 시간이 더 짧을 수도 있는데,  이미 방문 표시가 되어있어서 못 가는 경우가 있다)

* 방문을 표시하는 visited 는 3차원으로 설정해서 좌표와 방향까지 저장을 해준다. 

 

 

#include <iostream> #include <vector> #include <cstring> #include <queue> #include <functional> #define INF 987654321 using namespace std; //SWEA 보급로 [1249](https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD) int map[101][101]; int dp[101][101]; bool visited[101][101][4]; int n; int ans = INF; int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1}; typedef struct Q { int cost, dir, x, y; } Q; bool operator<(const Q &a, const Q &b) { return a.cost > b.cost; } void bfs() { priority_queue<Q> q; q.push({0, 0, 0, 0}); while (!q.empty()) { Q qq = q.top(); q.pop(); int cost = qq.cost; int dir = qq.dir; int x = qq.x; int y = qq.y; if (x == n - 1 && y == n - 1) { ans = min(ans, cost); continue; } if (visited[x][y][dir]) continue; visited[x][y][dir] = true; for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; if (dp[x][y] != INF && dp[nx][ny] > dp[x][y] + map[nx][ny]) { dp[nx][ny] = dp[x][y] + map[nx][ny]; q.push({dp[nx][ny], i, nx, ny}); } } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; for (int tc = 1; tc <= t; tc++) { cin >> n; memset(visited, 0, sizeof(visited)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { char c; cin >> c; map[i][j] = c - '0'; dp[i][j] = INF; } } ans = INF; dp[0][0] = 0; bfs(); cout << "#" << tc << " " << ans << '\n'; } return 0; }