백준 4485 - 녹색 옷 입은 애가 젤다지?(C++)

문제 링크입니다. https://www.acmicpc.net/problem/4485

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

다익스트라 알고리즘과 4방향 탐색이 합쳐진 문제입니다.

(1 , 1)에서 시작해 (N, N)까지 갔을 때의 최소 비용을 구하는 문제입니다.

최소 비용만 구하면 됨으로, 다익스트라 알고리즘을 이용하여 푸는 문제입니다.

기존 다익스트라 알고리즘 문제와 차이점은 노드로 주어지는 것이 아닌, 좌표로써 값이 주어진다는 것입니다.

 

따라서 저는 2차원 배열을 이용해, 해당 좌표에서의 비용, 최소 비용을 저장했습니다.

 

다익스트라 알고리즘 코드입니다.

void Dijstra(int x, int y){
	Distance[x][y] = map[x][y];
	q.push({map[x][y],{x,y}});
	while(!q.empty()){
		int cost = q.top().first;
		int X = q.top().second.first;
		int Y = q.top().second.second;
		check[X][Y] = 1;
		q.pop();
		for(int i = 0; i < 4; i++){
			int xx = X + dx[i];
			int yy = Y + dy[i];
			if(xx >= 1 && yy >= 1 && xx <= N && yy <= N){
				if(check[xx][yy] == 1) continue;
				if(Distance[xx][yy] > Distance[X][Y] + map[xx][yy]){
					Distance[xx][yy] = Distance[X][Y] + map[xx][yy];
					q.push({Distance[xx][yy], {xx,yy}});
				}
			}
		}
	}
}

처음은 (1 ,1)에서 시작하니, 해당 값을 받아주고 시작했습니다.

(1 , 1)의 최소 값은 map[1][1]의 값이니, 최소 비용을 저장하는 배열은 Distance에 해당 값을 넣고 시작했습니다.

탐색을 위해 우선 순위 큐에 (map[1][1] , 1, 1)의 값을 넣어줬습니다.

 

우선 순위 큐를 통해, 비용이 가장 작은 위치를 얻을 수 있습니다. 따라서 해당 위치에서 4방향 탐색을 통해 갈 수 있는 곳을 찾습니다.

갈 수 있는 곳을 찾았다면, 해당 위치의 최소 비용이 이번에 움직일 위치에서 사용하는 비용보다 크다면, 바꿔준 뒤 큐에 넣어줍니다.

-> 해당 과정을 반복하면 (N , N)에서의 최소 비용을 구할 수 있습니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <cmath>
#include <cstring>
#define INF 987654321

using namespace std;

int N;
int map[126][126];
int check[126][126];
int Distance[126][126];
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>> , greater<pair<int,pair<int,int>>>> q;

void reset_distance(){
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= N; j++){
			Distance[i][j] = INF;
			check[i][j] = 0;
		}
	}
	
}

void Dijstra(int x, int y){
	Distance[x][y] = map[x][y];
	q.push({map[x][y],{x,y}});
	while(!q.empty()){
		int cost = q.top().first;
		int X = q.top().second.first;
		int Y = q.top().second.second;
		check[X][Y] = 1;
		q.pop();
		for(int i = 0; i < 4; i++){
			int xx = X + dx[i];
			int yy = Y + dy[i];
			if(xx >= 1 && yy >= 1 && xx <= N && yy <= N){
				if(check[xx][yy] == 1) continue;
				if(Distance[xx][yy] > Distance[X][Y] + map[xx][yy]){
					Distance[xx][yy] = Distance[X][Y] + map[xx][yy];
					q.push({Distance[xx][yy], {xx,yy}});
				}
			}
		}
	}
}

void solve(int cnt){
	reset_distance();
	Dijstra(1,1);
	printf("Problem %d: %d\n", cnt, Distance[N][N]);
}

int main()
{
	cin.tie(0);
	cout.tie(0);
	int cnt = 1;
	while(1){
		cin >> N;
		if(N == 0) break;
		for(int i = 1; i <= N; i++){
			for(int j = 1; j <= N; j++){
				cin >> map[i][j];
			}
		}
		solve(cnt++);		
	}
	return 0;
}

 

질문 및 조언 댓글 남겨주세요