[백준 4485] 젤다

https://www.acmicpc.net/problem/4485

4485번: 녹색 옷 입은 애가 젤다지?

 

요구사항

제일 오른쪽 밑에 도달하기 까지 최소의 금액을 잃는 경우 구하기

 

풀이

cost[][]를 무한으로 지정한다

도달할때 최소로 갱신이 된다면 진행하는 형태의 다익스트라 알고리즘을 사용한다.

 

#include <iostream>
#include <queue>

using namespace std;
int map[126][126];
int dist[126][126];
const int INF = 0x7fffffff;
int n;
int dc[4] = { 0,-1,0,1 };
int dr[4] = { -1,0,1,0 };
int main() 
{
	int cnt = 0;
	while (true) {
		cnt++;
		scanf("%d", &n);
		if (n == 0) {
			break;
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				scanf("%d", &map[i][j]);
				dist[i][j] = INF;
			}
		}
		priority_queue<pair<int ,pair<int, int>>> q;
		q.push({ -map[0][0], {0,0} });
		dist[0][0] = map[0][0];
		while (!q.empty()) {
			int r = q.top().second.first;
			int c = q.top().second.second;
			int cost = -q.top().first;
			//cout << "R" << r << "C" << c << endl;
			q.pop();
			for (int i = 0; i < 4; i++) {
				int nr = r + dr[i];
				int nc = c + dc[i];
				if (nr < 0 || nc < 0 || nr >= n || nc >= n) {
					continue;
				}
				if (dist[nr][nc] > map[nr][nc] + cost) {
					dist[nr][nc] = map[nr][nc] + cost;
					//cout << "NR"<<nr << " " << nc << " " << -dist[nr][nc] << endl;
					
					q.push({ -dist[nr][nc],{nr,nc} });
				}
			}
		}
		printf("Problem %d: %d\n", cnt, dist[n - 1][n - 1]);
	}
}