[알고리즘] 백준 2665번: 미로만들기 (C++)

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

2665번: 미로만들기

[솔루션]

1) 벽 한 번 부술 때, 비용을 1로 처리한다.

2) 다익스트라를 돌려서 n행 n열까지 가는 데에 벽을 부순 최소 횟수를 구한다. (다익스트라 이용)

+) 모든 가중치가 1이라 BFS로도 풀릴 거 같다.

 

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

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

typedef struct {
	int y, x;
} Direction;

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

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

int n;

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>(n + 1, INF));
	dist[row][col] = 0;
	pq.push({ {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;
			int nextCost;
			if (dy <= n && dy >= 1 && dx <= n && dx >= 1) {
				if (map[dy][dx] == 1) {
					nextCost = 0;
				}
				else {
					nextCost = 1;
				}

				if (cost + nextCost < dist[dy][dx]) {
					dist[dy][dx] = cost + nextCost;
					pq.push({ {dy, dx}, dist[dy][dx] });
				}
			}
		}
	}

	return dist;
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		string value;
		cin >> value;
		for (int j = 1; j <= n; j++) {
			map[i][j] = value[j - 1] - '0';
		}
	}

	vector<vector<int>> temp = dijkstra(1, 1);
	cout << temp[n][n] << '\n';

	return 0;
}