์๊ณ ๋ฆฌ์ฆ
- ๋ฌธ์ ๋ฅผ ํด์ํ๋ฉด, ํ ์ ์์ ๋ค๋ฅธ ํ ์ ๊น์ง ๊ฐ๋๋ฐ ์ต์๊ฒฝ๋ก๋ฅผ ์ฐพ๋ ๋ฌธ์ ๋ก ํด์ํ ์ ์๋ค.
- ๋ฐ๋ผ์ ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ์ ์ฉํ๋ฉด ์ฝ๊ฒ ํ์์๋ค.
- ์ด๋ ํ ์นธ์ ์ ์ฅ๋ ๊ฐ์, ๊ทธ ์นธ์ผ๋ก ์ ๊ทผํ๋ ๊ฒฝ๋ก์ ๊ธธ์ด๋ก ์นํํ์ฌ ํ.
์ฌ๋ด
- ๋ฌธ์ ๋ด์ ๋ค์ต์คํธ๋ผ๋ผ๋ ๊ฝค๋ ๋ง์ ํํธ๊ฐ ์์์ผ๋, dfs์ ์ฌ๋ก์กํ์ ์ค๋ ๊ฑธ๋ ธ๋ค.
- 2์ฐจ์ ๋ฐฐ์ด์ ๋์์ผ๋ก ๋ค์ต์คํธ๋ผ๋ฅผ ๊ตฌํํ ๋ฌธ์ ๋ ์ฒ์์ด์๊ธฐ์ ๊ฝค๋ ์ ์ ํ๋ค.
์ฝ๋
#include <iostream>
#include <queue>
#define INF 2000000000
using namespace std;
int n, map[125][125], os[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} }, save[125][125];
bool check[125][125];
priority_queue<pair<int, pair<int,int>>> q;
int dijk();
int min(int a, int b) {
return a > b ? b : a;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int idx = 1;
while (true) {
cin >> n;
if (n == 0)
break;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
cin >> map[i][j];
check[i][j] = false;
}
cout << "Problem " << idx++ << ": " << dijk() << endl;
}
}
int dijk() {
q.push({ -map[0][0] , {0,0 } });
save[0][0] = map[0][0];
while (!q.empty()) {
int cur = -q.top().first, r = q.top().second.first, c = q.top().second.second;
q.pop();
if (check[r][c])
continue;
check[r][c] = true;
save[r][c] = cur;
for (int i = 0; i < 4; i++) {
int nr = r + os[i][0], nc = c + os[i][1];
if (nr >= 0 && nr < n && nc >= 0 && nc < n && !check[nr][nc]) {
int ncur = cur + map[nr][nc];
q.push({ -ncur, {nr, nc} });
}
}
}
return save[n - 1][n - 1];
}