백준 1261 (알고스팟)

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

1261번: 알고스팟

해당 문제는 M * N 크기의 미로가 주어지며 (벽은 1 , 빈 공간 0) 해당 미로의 1 by 1 의 위치에서 N M 의 위치 까지 이동한다고 했을 때 가장 적은 수의 벽을 깨고 갈 수 있는 경우에 깬 벽의 횟수를 구하는 문제이다.

일반적인 Queue를 사용한 BFS탐색을 이용할 경우 결국 모든 경우를 모두 순회 해야 함으로 Queue 메모리 초과가 발생한다.

따라서 Deque 를 사용하여 이동하는 위치가 벽일 경우에는 qu의 뒤쪽에 Push 하여 우선순위를 낮추고 이동하는 위치가 빈 공간 일 경우에는 qu의 앞에 Push 하여 우선순위를 높이는 형태로 다음에 이동할 위치의 우선순위를 결정한다. 이렇게 Push 한 정보를 qu의 front 부터 pop하여 벽을 깨지 않는 경우먼저 탐색하면 된다.

 

#include <iostream>
#include <deque>

using namespace std;

struct Node{
	int y, x;
	int breakWall;
};
int n, m;
int checkY[4] = { 0, 0, +1, -1 };
int checkX[4] = { 1, -1, 0, 0 };
char map[101][101];
int visit[101][101];
int res = 0;

void bfs(){
	deque<Node> qu;
	qu.push_front({ 1, 1, 0 });
	visit[1][1] = 1;

	while (!qu.empty()){
		Node now = qu.front();
		qu.pop_front();
		for (int i = 0; i < 4; ++i){
			int dy = now.y + checkY[i];
			int dx = now.x + checkX[i];
			if (dy <= 0 || dx <= 0 || dy > n || dx > m) continue;
			if (visit[dy][dx] == 1) continue;
			visit[dy][dx] = 1;
			if (dy == n && dx == m){
				res = now.breakWall;
				return;
			}

			else if (map[dy][dx] == '0'){
            // 벽이 아닐 경우 qu의 front에 Push
				qu.push_front({ dy, dx, now.breakWall });
			}

			else if (map[dy][dx] == '1'){
             // 벽일 경우 qu의 Back에 Push
				qu.push_back({ dy, dx, now.breakWall + 1 });
			}
		}
	}
	return;
}

int main(){
	//freopen_s(new FILE*, "tes.text", "r", stdin);
	cin >> m >> n;


	for (int i = 1; i <= n; ++i){
		for (int j = 1; j <= m; ++j){
			cin >> map[i][j];
		}
	}

	bfs();

	cout << res << endl;

}