[백준/BOJ] 백준 4485번 : 녹색 옷 입은 애가 젤다지?

www.acmicpc.net/problem/4485

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

각 지점의 도둑 루피를 비용으로 하여 (0,0) 지점에서 (n-1, n-1) 지점으로 가는 최소비용을 구하는 방법으로 문제를 해결했다. start지점에서도 해당 구간의 도둑루피만큼 비용이 있다. 최소비용을 구하는 방법은 다익스트라 알고리즘을 사용했다.

 

코드

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

int n;
int board[125][125];
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

//다익스트라 알고리즘을 이용하여 start에서 dest로 가는 최소 비용을 구한다
int Solve(pair<int,int> start, pair<int,int> dest)
{
	vector<vector<int>> short_dist(n, vector<int>(n, 987654321)); //start에서 각 지점으로 가는 최소 비용
	priority_queue<pair<int, pair<int,int>>> pq;

	short_dist[start.first][start.second] = board[start.first][start.second]; //start지점에서도 해당 구간의 도둑루피만큼 비용이 있다
	pq.push(make_pair(-board[start.first][start.second], start));

	while (!pq.empty())
	{
		pair<int, int> here = pq.top().second;
		int here_cost = -pq.top().first;
		pq.pop();

		if (here_cost > short_dist[here.first][here.second])
			continue;

		//here에서 갈수 있는 지점을 확인
		for (int i = 0; i < 4; i++)
		{
			pair<int, int> there = make_pair(here.first + dxdy[i][0], here.second + dxdy[i][1]);

			if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < n)
			{
				int there_cost = here_cost + board[there.first][there.second];

				if (there_cost < short_dist[there.first][there.second])
				{
					short_dist[there.first][there.second] = there_cost;
					pq.push(make_pair(-there_cost, there));
				}
			}
		}
	}

	return short_dist[dest.first][dest.second];
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int k;
	int cnt = 0;

	while (1)
	{
		cnt++;

		cin >> n;

		if (n == 0)
			break;

		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
			{
				cin >> k;
				board[i][j] = k;
			}

		cout <<"Problem "<< cnt <<": " << Solve(make_pair(0, 0), make_pair(n - 1, n - 1)) << "\n";
	}

	return 0;
}