1261. 알고스팟

Problem

• 문제링크

Solution

• 벽을 최소한으로 부수면서 목적지에 도착해야 한다.
• 벽을 부수지 않고 갈 경우 비용은 0
• 벽을 부수고 갈 경우 비용은 1
• 따라서 deque를 사용하여 BFS 탐색을 한다.

1. 벽을 부수지 않는 경우 front에 넣는다.
2. 벽을 부수는 경우 back에 넣는다.
3. front 부분을 탐색하고 pop한다.
   그래야 벽을 최소한으로 부수면서 visit(방문) 표시가 가능하다.

1 Try

#include <cstdio>
#include <tuple>
#include <deque>
using namespace std;
int N, M;
int map[100][100];
bool visit[100][100];
int cnt[100][100];
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1 ,1 };
void Input() {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < M; ++i) {
		for (int j = 0; j < N; ++j) {
			scanf("%1d", &map[i][j]);
		}
	}
}
void BFS() {
	deque <pair<int, int>> q;
	q.push_front({ 0, 0 });
	visit[0][0] = true;
	while (!q.empty()) {
		int x, y;
		tie(x, y) = q.front();
		q.pop_front();
		for (int dir = 0; dir < 4; ++dir) {
			int d_x = x + dx[dir];
			int d_y = y + dy[dir];
			if (d_x == N - 1 && d_y == M - 1) {
				cnt[d_x][d_y] = cnt[x][y];
				return;
			}
			if (d_x > -1 && d_y > -1 && d_x < M && d_y < N) {
				if (visit[d_x][d_y]) continue;
				if (map[d_x][d_y] == 1) {
					cnt[d_x][d_y] = cnt[x][y] + 1;
					q.push_back({ d_x, d_y });
				}
				else {
					cnt[d_x][d_y] = cnt[x][y];
					q.push_front({ d_x, d_y });
				}
				visit[d_x][d_y] = true;
			}
		}
	}
}
int main() {
	Input();
	BFS();
	printf("%d\n", cnt[M - 1][N - 1]);
	return 0;
}