[BOJ]백준 2665번: 미로 만들기/Dijkstra

www.acmicpc.net/problem/2665

2665번: 미로만들기

미로 만들기 문제 2차원 배열에서의 최단거리 문제이다.

벽부수고 이동하기와 미로만들기처럼 벽(cost가 높은 좌표)를 최소화해서 목적지에 도착하기 위해서는, 가중치 그래프의 최단거리를 이용해야 한다

따라서 2차원 배열에 다익스트라 알고리즘을 적용하면 문제를 해결할 수 있다

문제에서는 흰색(지나갈 수 있는 곳)을 1, 검은색을 0으로 해줬는데 입력받은 뒤 이를 완전히 뒤집고

다익스트라 알고리즘을 통해 (N,N)으로 갈 수 있는 최단거리를 구해주면 끝

#include <cstdio>
#include <algorithm>
#include <queue>
#define INF 987654321
using namespace std;
typedef struct { int x, y; }point;
struct compare {
	bool operator()(pair<int, point> a, pair<int, point> b) {
		return a.first < b.first;
	}
};
int n, arr[51][51], dist[51][51], dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 };
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++)for (int j = 0; j < n; j++) {
		scanf("%1d", &arr[i][j]);
		arr[i][j] ^= 1;
	}
	fill(&dist[0][0], &dist[n - 1][n], INF);
	priority_queue<pair<int, point>, vector<pair<int, point>>, compare> pq;

	pq.push({ 0,{0,0} });
	dist[0][0] = 0;
	while (!pq.empty()) {
		int cost = -pq.top().first;
		point cur = pq.top().second;
		pq.pop();

		for (int i = 0; i < 4; i++) {
			int nx = cur.x + dx[i], ny = cur.y + dy[i];
			if (nx < 0 || nx >= n || ny < 0 || ny >= n)continue;
			if (dist[cur.y][cur.x] + arr[ny][nx] < dist[ny][nx]) {
				dist[ny][nx] = dist[cur.y][cur.x] + arr[ny][nx];
				pq.push({ -dist[ny][nx],{nx,ny} });
			}
		}
	}
	printf("%d", dist[n - 1][n - 1]);
	return 0;
}

참 쉽죠?