백준 2665번, 미로만들기

 

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

2665번: 미로만들기

요약

 

(1,1) 지점에서 (N,N) 지점으로 이어지는 미로를 만든다.

---

1. 미리 정해진 방의 상태가 주어진다. 이때, 흰 방은 조작 없이 지나갈 수 있고, 검은 방은 1회의 조작 후 지나갈 수 있다.

 

2. 인접한 흰 방으로의 이동은 비용이 0, 인접한 검은 방으로의 이동은 비용이 1인 그래프로 바꾸어 다익스트라로 풀이할 수 있다.

 

3. 다익스트라의 시간 복잡도는 $O\left ( \left| E\right|log\left|E \right| \right )$이고, 정점의 개수가 최대 50 * 50 = 2500개, 간선의 개수가 최대 4 * V이므로 1초 안에 처리 가능하다.

 

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;

struct cmp {
	bool operator() (pair<int, pair<int, int>> A, pair<int, pair<int, int>> B) {
		return A.first > B.first;
	}
};

int N;
int arr[50][50];
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };
int dist[50][50];

void Dijkstra(int x, int y);

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < N; j++) {
			arr[i][j] = s[j] - '0';
			arr[i][j] ^= 1;
		}
	}
	Dijkstra(0, 0);
	cout << dist[N - 1][N - 1];
	return 0;
}

void Dijkstra(int x, int y) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) dist[i][j] = INF;
	}
	priority_queue <pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, cmp> pq;
	dist[y][x] = 0;
	pq.push({ 0, {x,y} });
	while (pq.size()) {
		int now_x = pq.top().second.first;
		int now_y = pq.top().second.second;
		int val = pq.top().first;
		pq.pop();
		if (dist[now_y][now_x] < val) continue;
		for (int i = 0; i < 4; i++) {
			int nx = now_x + dx[i];
			int ny = now_y + dy[i];
			if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;
			int new_val = val + arr[ny][nx];
			if (dist[ny][nx] > new_val) {
				dist[ny][nx] = new_val;
				pq.push({ new_val, {nx,ny} });
			}
		}
	}
}