백준 4485 녹색 옷 입은 애가 젤다지?

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다.

 

이문제는 이전글인 1261번 알고스팟과 유사한 문제입니다.(거의 동일합니다)

 

시작점에서 N-1,N-1까지 가면서 잃는 금액이 가장 최소가 될때 금액을 구하는 문제입니다. 따라서 다익스트라 알고리즘을 통해 최단경로를 구해야 하고

 

그래프가 N*N행렬 형태로 주어지고 각 노드에서는 상하좌우로 이동할수 있으므로 각 노드는 상하좌우의 노드와 연결되어 있다고 생각 하고 풀면 됩니다.

 

다음은 코드입니다.

 

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define INF 987654321
 
int arr[130][130];
priority_queue<pair<int, pair<int, int>> > pq;
int answer[130][130];
int nextx[4] = {0, 1, 0, -1};
int nexty[4] = {1, 0, -1, 0};
int N;

void dijkstra() {
	
	answer[1][1] = arr[1][1];
	pq.push(make_pair(-answer[1][1], make_pair(1, 1)));
	while(!pq.empty()) {
		
		int cost = -pq.top().first;
		int x = pq.top().second.first;
		int y = pq.top().second.second;
		pq.pop();
		
		for(int i = 0; i < 4; i++) {
			int xx = x + nextx[i];
			int yy = y + nexty[i];
			
			if(xx < 1 || xx > N || yy < 1 || yy > N) continue;
			
			int nextDist = cost + arr[xx][yy];
			if(answer[xx][yy] > nextDist) {
				answer[xx][yy] = nextDist;
				pq.push(make_pair(-nextDist, make_pair(xx, yy)));
			}
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int num = 1;
	while(cin >> N) {
		if(N == 0) break;
		fill(&answer[0][0], &answer[129][130], INF);
		for(int i = 1; i <= N; i++)
			for(int j = 1; j <= N; j++) 
					cin >> arr[i][j];
		dijkstra();
		cout<<"Problem "<<num<<": "<<answer[N][N]<<'\n';
		num++;
	}
	
	return 0;
}