백준 1261번: 알고스팟

[문제 링크]

1261번: 알고스팟

---

시작지점(1,1) 에서 도착지점(N,M) 으로 가는 최단 경로를 구하는 문제였다.

 

벽을 최대한 안부시는 경로로 이동해야 하기 때문에 방문표시를 하면 안된다.

따라서, 다익스트라 알고리즘을 이용하여 구현하였다.

---

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

const int INF = 987654321;
int N, M;
char board[101][101];
int dy[4] = { 0, 0, 1, -1 };
int dx[4] = { 1, -1, 0, 0 };

int dijkstra() {
	vector<vector<int>> dist(101, vector<int>(101, INF));
	dist[1][1] = 0;

	priority_queue <pair<int, pair<int, int>>> pq;
	pq.push({ 0, {1,1} });

	while (!pq.empty()) {
		int hy = pq.top().second.first;
		int hx = pq.top().second.second;
		int isBreak = -pq.top().first;
		pq.pop();

		if (dist[hy][hx] < isBreak) continue;

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

			if (ny > 0 && ny <= N && nx > 0 && nx <= M) {
				int nextBreak = isBreak + board[ny][nx] - '0';

				if (dist[ny][nx] > nextBreak) {
					dist[ny][nx] = nextBreak;
					pq.push({ -nextBreak, {ny, nx} });
				}
			}
		}
	}

	return dist[N][M];
}

int main(void) {
	cin >> M >> N;

	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			cin >> board[i][j];

	cout << dijkstra() << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 165 day