[SWExpert] 보급로

• 입력: 테스트케이스 T, 가로세로 길이 N, (i, j)를 복구하는 데 드는 비용 N*N
• 출력: (0, 0) => (n - 1, n - 1) 가는 복구 최솟값
• 알고리즘: 다익스트라
• 소스코드
#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <vector> #include <string> #include <iostream> #include <queue> #include <functional> using namespace std; #define fee pair<int, pair<int, int> > #define mp(x, y) make_pair(x, y) #define pointX(fee) fee.second.first #define pointY(fee) fee.second.second string map[100]; int mov[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} }; int restore(const int n) { priority_queue<fee, vector<fee>, greater<fee> > min; min.push(mp(0, mp(0, 0))); int result = 90001; vector<vector<int> > cache(n, vector<int>(n, 900001)); while (!min.empty()) { fee here = min.top(); min.pop(); if (pointX(here) == n - 1 && pointY(here) == n - 1) { return here.first; } if (cache[pointX(here)][pointY(here)] <= here.first) continue; cache[pointX(here)][pointY(here)] = here.first; for (int i = 0; i < 4; i++) { if (pointX(here) + mov[i][0] < 0 || pointX(here) + mov[i][0] >= n || pointY(here) + mov[i][1] < 0 || pointY(here) + mov[i][1] >= n) continue; min.push(mp(here.first + (map[pointX(here)][pointY(here)] -'0'), mp(pointX(here) + mov[i][0], pointY(here) + mov[i][1]))); } } return result; } int main() { freopen("sample_input.txt", "r", stdin); int testcase, n; scanf("%d", &testcase); for (int TC = 1; TC <= testcase; TC++) { scanf("%d", &n); for (int i = 0; i < n; i++) { cin >> map[i]; } int min = 90001; printf("#%d %d\n", TC, restore(n)); } return 0; }

DFS로 풀려다가 경우의 수가 너무 많아서 시간초과가 났다. 최솟값이기 때문에 다익스트라를 이용하여 가장 빨리 나온 최솟값을 출력하면 된다. BFS라 생각했는데 어면히 다익스트라인거 같다. 시간이 그렇게 빠른거 같지는 않다.