[알고리즘] 백준 4485번: 녹색 옷 입은 애가 젤다지? (C++)

https://www.acmicpc.net/problem/4485

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

2차원 배열 형식의 다익스트라는 처음이었다.

헷갈릴 수 있었던 포인트는

1) 구조체를 먼저 선언

2) 비용 초기값 0으로 초기화하지 않기

3) 복잡한 타입으로 인한 지저분한 코드

 

#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#define MAX 125
#define INF 987654321
using namespace std;

int graph[MAX][MAX];

typedef struct {
	int y, x;
} Direction;

struct cmp {
	bool operator()(pair<Direction, int>& a, pair<Direction, int>& b) {
		return a.second > b.second;
	}
};

Direction dir[4] = { {-1, 0}, {1, 0}, {0, 1}, {0, -1} };

vector<vector<int>> dijkstra(int row, int col, int n) {
	priority_queue<pair<Direction, int>, vector<pair<Direction, int>>, cmp> pq;
	vector<vector<int>> dist(n, vector<int>(n, INF));
	pq.push({{ row, col }, graph[row][col]});
	dist[row][col] = graph[row][col];

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

		pq.pop();
		for (int i = 0; i < 4; i++) {
			int dy = y + dir[i].y;
			int dx = x + dir[i].x;
			int nextCost = graph[dy][dx];
			if (dy < n && dy >= 0 && dx < n && dx >= 0) {
				if (cost + nextCost < dist[dy][dx]) {
					dist[dy][dx] = cost + nextCost;
					pq.push({ { dy, dx }, dist[dy][dx] });
				}
			}
		}
	}
	return dist;
}

int main() {
	int cnt = 1;
	for (;;) {
		int n;
		cin >> n;
		if (n == 0) {
			break;
		}

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

		vector<vector<int>> temp = dijkstra(0, 0, n);
		cout << "Problem " << cnt << ": " << temp[n - 1][n - 1] << '\n';
		cnt++;
	}
	return 0;
}