[백준] 2665번 미로만들기 C++ 코드

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <deque>
#include <cstring>

using namespace std;
struct edge {
	int x, y, cnt;
};
const int dx[] = { 0, 0, 1, -1 };
const int dy[] = { 1, -1, 0, 0 };
int n, res, visited[53][53];
string s;
char a[53][53];

int bfs() {
	deque<edge> dq;
	dq.push_back({ 0, 0, 0 });
	visited[0][0] = 1;
	while (!dq.empty()) {
		int px = dq.front().x;
		int py = dq.front().y;
		int cnt = dq.front().cnt;
		if (px == (n - 1) && py == (n - 1)) return cnt;
		dq.pop_front();
		for (int i = 0; i < 4; i++) {
			int nx = px + dx[i];
			int ny = py + dy[i];
			if (nx >= n || ny >= n || nx < 0 || ny < 0 || visited[nx][ny]) continue;
			if (a[nx][ny] == '1') {
				visited[nx][ny] = visited[px][py] + 1;
				dq.push_front({ nx, ny, cnt });
			}
			else if (a[nx][ny] == '0') {
				visited[nx][ny] = visited[px][py] + 1;
				dq.push_back({ nx, ny, cnt + 1 });
			}
		}

	}
	return 987654321;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s;
		for (int j = 0; j < n; j++) {
			a[i][j] = s[j];
		}
	}

	cout << bfs() << '\n';
	return 0;
}

풀이

최단거리를 구하고, 가중치가 0 또는 1이라서 0-1 bfs로 해결했다. 흰 방의 경우는 가중치가 없으므로 우선순위가 높다. 따라서 덱의 앞에 삽입한다. 검은 방의 경우는 가중치가 1이라 덱의 뒤에 삽입을 했다. 가중치가 0인 경로를 우선 탐색하므로, 벽을 부수지 않고 갈 수 있는 경로를 먼저 확인한다. 그리고 벽을 부수는 경로는 나중에 탐색하므로 최단경로와 최소 비용(벽을 최소로 부수는 것)을 보장한다.