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

 

www.acmicpc.net/problem/4485

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

(저도 이 문제를 보기 전까지 녹색 옷 입은 애가 젤다인 줄 알았습니다.)

n x n 동굴에 주인공이 0,0 지점에 있다면 n-1, n-1 까지 도달할 때 최소한의 검정 루피를 밟고 가도록 하는 문제입니다. 

다익스트라 알고리즘을 이용해 시작지점이 0,0으로 정해져 있으므로 모든 지점을 탐색하면서 최소 경로로 만들어주면 됩니다. 

그리고 마지막으로 n-1, n-1 지점의 최소 경로 값을 구해주면 됩니다.

 

또한 테스트케이스에 따라 다르겠지만, n<=125 이므로 다익스트라를 일반 큐를 이용해 적용 시 최악의 경우 맵 전체 노드가 n^2 개, 다익스트라 탐색에 O(n^2) 이므로 총 O(n^4) 이 듭니다. 그래서 우선순위 큐를 이용해 다익스트라 알고리즘을 적용하였습니다. 

(우선순위 큐 적용 시 평균 O(nlogn))

 

코드는 다음과 같습니다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>

using namespace std;

int problem_num = 0;
int n = 1;
int map[125][125];
int dijk[125][125];
int dy[4] = { 0,0,1,-1 };
int dx[4] = { 1,-1,0,0 };
int inf = 987654321;

void init()
{
	memset(map, sizeof(map), 0);
	memset(dijk, sizeof(dijk), 0);
	problem_num++;

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			dijk[i][j] = inf;
		}
	}
}

// 다익스트라 알고리즘으로 dijk[n][n] 구하면 된다.
// n<=125 이므로 우선순위 큐 이용해서 하기
void dijkstra(int start_y, int start_x)
{
	// 우선순위 큐 : { (y,x)까지 비용, {y,x}}, 오름차순으로
	priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>> >q;
	q.push({ map[start_y][start_x], {start_y, start_x} });
	dijk[start_y][start_x] = map[start_y][start_x];

	while (!q.empty())
	{
		int cost = q.top().first;
		int y = q.top().second.first;
		int x = q.top().second.second;

		q.pop();

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (ny < 0 || ny >= n || nx < 0 || nx >= n)
				continue;

			if (dijk[ny][nx] > (cost + map[ny][nx])) {
				int new_cost = cost + map[ny][nx];
				q.push({ new_cost,{ny, nx} });
				dijk[ny][nx] = new_cost;
			}
		}
	}
}

void print_result()
{
	cout << "Problem " << problem_num << ": " << dijk[n - 1][n - 1] << '\n';
}

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

	while (1)
	{
		init();

		if (n == 0)
			break;

		dijkstra(0, 0);
		print_result();
	}
}