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

사용한 알고리즘 : 다익스트라

우선 이 문제와 같이 그래프 상에서 상하좌우 를 이동하는 경우 제가 짠 것과 같이 X 행 Y 열 이동하는 행렬을 별도로 만들어 놓고 for 구문으로 4번씩 보며 이동하면 편합니다..... ( 혹은 행열을 하나로 묶어서 [2][4] 행렬로 만들어도 편해요...)

각 위치의 도둑루피의 값을 cave[130][130] 에 저장하고 dist[130][130] 으로 [0][0]에서 각 위치까지 얼마의 값으로 갈 수 있는지 알아봤습니다.

우선 모든 dist 값을 INF 값으로 설정 후,

dist[0][0] 값을 0 으로 하고 이 위치 (0,0)을 pq(priority_queue)에 넣고 시작 합니다.

pq에서 위치의 값을 하나씩 빼내, 이 위치를 (a,b) 라 하면,

이 위치에서 이동가능한 상하좌우(X,Y) 중에서, dist[X][Y] > dist[a][b] + cave[X][Y] (도둑루피값)

인 경우 값을 최신화 하고,

최신화 된 위치를 다시 pq에 넣어 돌렸습니다.

참고로 출력이 "Problem 1: 20" 꼴인데, 띄어쓰기를 잘못하여 많이 틀렸습니다...

여러분들은 이런 실수 없으시길 바라겠습니다......

	#include <bits/stdc++.h>
	using namespace std;
	#define pii pair<int, int>
	const int INF = 987654321;
	int N, temp;
	int cave[130][130];
	int dist[130][130];
	int goX[4] = {0,0,1,-1};
	int goY[4] = {1,-1,0,0};
	struct cmp{
	bool operator()(const pii &t, const pii &u){
	if(dist[t.first][t.second] == dist[u.first][u.second])
	return t.first+t.second < u.first+u.second;
	return dist[t.first][t.second] > dist[u.first][u.second];
	}
	};
	priority_queue<pii , vector<pii>, cmp> Que;
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	while(1){
	temp++;
	cin >> N;
	if(N==0) break;
	for (int i = 0; i < N; ++i){
	for (int j = 0; j < N; ++j){
	cin >> cave[i][j];
	dist[i][j] = INF;
	}
	}
	dist[0][0] = cave[0][0];
	Que.push(pii(0,0));
	while(!Que.empty()){
	pii now = Que.top();
	int a = now.first;
	int b = now.second;
	Que.pop();
	for (int i = 0; i < 4; ++i){
	int X = a + goX[i];
	int Y = b + goY[i];
	if(X<0 || X>=N || Y<0 || Y>=N) continue;
	if(dist[X][Y] > (dist[a][b]+cave[X][Y])){
	dist[X][Y] = dist[a][b]+cave[X][Y];
	Que.push(pii(X,Y));
	}
	}
	}
	cout << "Problem "<< temp << ": "<< dist[N-1][N-1] << '\n';
	}
	return 0;
	}

view raw BOJ 4485.cpp hosted with ❤ by GitHub