[알고리즘] 백준 1261번: 알고스팟 (C++)

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

1261번: 알고스팟

2차원 배열을 이용한 다익스트라 문제였다.

입력은 문자열을 처리해줘야 했으며 다음 노드로 가는 비용을 계산할 때 입력받은 2차원 배열을 이용하는 것을 까먹지 않으면 쉽게 풀리는 문제다.

[AC 코드]

#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#define MAX (100 + 1)
#define pii pair<int, int>
#define INF 987654321
using namespace std;

vector<pair<pii, int>> graph[MAX];
int map[MAX][MAX];
int n, m;

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

typedef struct {
	int y, x;
} Direction;
Direction dir[4] = { {-1, 0}, {1, 0}, {0, 1}, {0, -1} };

vector<vector<int>> dijkstra(int row, int col) {
	priority_queue<pair<pii, int>, vector<pair<pii, int>>, cmp> pq;
	vector<vector<int>> dist(n + 1, vector<int>(m + 1, INF));
	pq.push({ {row, col}, 0 });
	dist[row][col] = 0;
	while (!pq.empty()) {
		int y = pq.top().first.first;
		int x = pq.top().first.second;
		int cost = pq.top().second;

		pq.pop();
		if (dist[y][x] < cost) continue;

		for (int i = 0; i < 4; i++) {
			int dy = y + dir[i].y;
			int dx = x + dir[i].x;
			if (dy > n || dy < 1 || dx > m || dx < 1) continue;
			int nextCost = map[dy][dx];
			if (cost + nextCost < dist[dy][dx]) {
				dist[dy][dx] = cost + nextCost;
				pq.push({ {dy, dx}, dist[dy][dx] });
			}
		}
	}

	return dist;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> m >> n;
	for (int i = 1; i <= n; i++) {
		string value;
		cin >> value;
		for (int j = 0; j < value.size(); j++) {
			map[i][j + 1] = value[j] - '0';
		}
	}

	vector<vector<int>> temp = dijkstra(1, 1);
	cout << temp[n][m];
	return 0;
}