백준/4485/다익스트라/녹색 옷입은 애가 젤다지?

백준/4485/다익스트라/녹색 옷입은 애가 젤다지?

문제 해석

젤ㄷ..아니 링크가 0,0 좌표에서 N-1,N-1 좌표까지 갈 때 잃는 보석의 수를 최소로 할 때 이 최소 잃는 보석의 수를 구하는 문제입니다.

문제 풀이

1. map 배열안에 해당 칸을 이동 할때 잃는 보석의 수를 저장한다.
2. 현재 배열에서 상하좌우로 움직이면서 _min 배열안에 잃는 보석의 수를 저장해나간다. 이 때 해당 칸에 이미 잃는 최소의 보석의 개수가 저장되어있다면, 현재 이동은 무의미하므로 큐에 넣지 않는다.
3. 마지막으로 n-1,n-1에 기록된 최소 보석의 수를 출력한다.

1. map 배열안에 해당 칸을 이동 할때 잃는 보석의 수를 저장한다.

for (int y = 0;y < N;y++)
{
	for (int x = 0;x < N;x++)
	{
		cin >> map[y][x];
	}
}

2. 현재 배열에서 상하좌우로 움직이면서 _min 배열안에 잃는 보석의 수를 저장해나간다. 이 때 해당 칸에 이미 잃는 최소의 보석의 개수가 저장되어있다면, 현재 이동은 무의미하므로 큐에 넣지 않는다.

while (!q.empty())
{
	auto cur = q.front(); q.pop();
	for (int dir = 0;dir < 4;dir++)
	{
		int ny = cur.first + dirY[dir];
		int nx = cur.second + dirX[dir];
		if (ny < 0 || nx < 0 || ny >= N || nx >= N)continue;
		if (_min[ny][nx] > _min[cur.first][cur.second] + map[ny][nx])
		{
			_min[ny][nx] = _min[cur.first][cur.second] + map[ny][nx];
			q.push({ ny,nx });
		}
	}
}

3. 마지막으로 n-1,n-1에 기록된 최소 보석의 수를 출력한다.

cout << "Problem " << solve++ << ": " << _min[N - 1][N - 1] << '\n';

풀이

첫번째 풀이

#include<iostream>
#include<queue>
#include<string.h>
using namespace std;

int map[125][125];
int _min[125][125];

int dirY[4] = { 1,0,-1,0 };
int dirX[4] = { 0,1,0,-1 };

queue<pair<int, int>>q;

int INF = 0x3f3f3f3f;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int solve = 1;
	while (true)
	{
		int N = 0;
		cin >> N;

		if (N == 0)
			break;

		for (int y = 0;y < N;y++)
		{
			for (int x = 0;x < N;x++)
			{
				cin >> map[y][x];
			}
		}

		for (int y = 0;y < N;y++)
		{
			::memset(_min[y], INF, sizeof(int) * N);
		}

		_min[0][0] = map[0][0];

		q.push({ 0,0 });

		while (!q.empty())
		{
			auto cur = q.front(); q.pop();
			for (int dir = 0;dir < 4;dir++)
			{
				int ny = cur.first + dirY[dir];
				int nx = cur.second + dirX[dir];
				if (ny < 0 || nx < 0 || ny >= N || nx >= N)continue;
				if (_min[ny][nx] > _min[cur.first][cur.second] + map[ny][nx])
				{
					_min[ny][nx] = _min[cur.first][cur.second] + map[ny][nx];
					q.push({ ny,nx });
				}
			}
		}

		cout << "Problem " << solve++ << ": " << _min[N - 1][N - 1] << '\n';
	}

	return 0;
}