์•Œ๊ณ ๋ฆฌ์ฆ˜

  • ๋ฌธ์ œ๋ฅผ ํ•ด์„ํ•˜๋ฉด, ํ•œ ์ ์—์„œ ๋‹ค๋ฅธ ํ•œ ์ ๊นŒ์ง€ ๊ฐ€๋Š”๋ฐ ์ตœ์†Œ๊ฒฝ๋กœ๋ฅผ ์ฐพ๋Š” ๋ฌธ์ œ๋กœ ํ•ด์„ํ•  ์ˆ˜ ์žˆ๋‹ค.
  • ๋”ฐ๋ผ์„œ ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ ์šฉํ•˜๋ฉด ์‰ฝ๊ฒŒ ํ’€์ˆ˜์žˆ๋‹ค.
    • ์ด๋•Œ ํ•œ ์นธ์— ์ €์žฅ๋œ ๊ฐ’์€, ๊ทธ ์นธ์œผ๋กœ ์ ‘๊ทผํ•˜๋Š” ๊ฒฝ๋กœ์˜ ๊ธธ์ด๋กœ ์น˜ํ™˜ํ•˜์—ฌ ํ’ˆ.

์—ฌ๋‹ด

  • ๋ฌธ์ œ ๋‚ด์— ๋‹ค์ต์ŠคํŠธ๋ผ๋ผ๋Š” ๊ฝค๋‚˜ ๋งŽ์€ ํžŒํŠธ๊ฐ€ ์žˆ์—ˆ์œผ๋‚˜, 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];
}