[C++] BOJ(백준) 2665 미로만들기

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

2665번: 미로만들기

 

BFS문제다.

 

일반 미로 문제에서 벽(검은방)을 부수고 갈 수 있는 미로로 생각하면 되는 문제다.

문제에서 구해야하는 건 미로의 최단 경로가 아닌 최대한 벽을 적게 만나는 경로를 찾는 것이다.

 

방문 배열을 이용해서 문제를 해결했다.

방문 배열에 지나간 검은 방의 개수를 저장하고

현재 이동하려는 방 까지의 검은 방의 개수가 이전에 방문했을 때의 검은 방의 개수보다 작다면 방문한다.

 

이 때 간과했던 점이 방문 배열 초기화다.

최솟값을 찾아 나가는 것이므로 방문 배열을 최댓값으로 초기화하고 시작해야한다.

 

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

int n, m;
int visit[50][50];
string arr[50];
queue<pair<int, int>> q;

int dr[4] = { 1, 0, -1, 0 };
int dc[4] = { 0, 1, 0, -1 };

void bfs() {
	q.push({ 0, 0 });
	visit[0][0] = 0;

	while (!q.empty()) {
		int r = q.front().first;
		int c = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int rr = r + dr[i];
			int cc = c + dc[i];

			if (rr < 0 || cc < 0 || rr >= n || cc >= n) continue;
			if (arr[rr][cc] == '1') {
				if (visit[r][c] < visit[rr][cc]) {
					q.push({ rr, cc });
					visit[rr][cc] = visit[r][c];
				}
			}
			else {
				if (visit[r][c] + 1 < visit[rr][cc]) {
					q.push({ rr, cc });
					visit[rr][cc] = visit[r][c] + 1;
				}
			}
		}
	}
}

int main() {
	// 입출력 속도 향상을 위함
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) visit[i][j] = 3000;

	bfs();
	cout<<visit[n-1][n-1];
}