알고리즘 :: 백준 :: BFS :: 1261 :: 알고스팟

문제

문제접근

문제 이해

• 대표적인 BFS 유형인 미로찾기 유형에서 벽을 부술 수 있는 조건이 추가된 문제입니다.
• 이 문제에는 함정이 있습니다. 구하고자 하는 것이 최소거리/최단거리가 아닌 부순 벽의 최소개수 입니다.
• 그렇다면 생각해봅시다. 임의의 점에서 인접한 다른 점을 갈 때 벽을 부수는 경우와 부수지 않는 경우로 나뉠 것입니다.
• 즉, 벽을 부순다면 가중치가 1, 벽을 부수지 않는다면 가중치가 0이라고 생각할 수 있습니다.
• 우리는 알고리즘 :: 백준 :: BFS :: 13549 :: 숨바꼭질3 (velog.io) 이 문제에서 가중치가 0 또는 1인 경우 어떻게 풀어야하는지에 대해 배웠습니다. 바로 deque을 사용해서 서로 다른 가중치를 push하는 방법을 다르게 하는 것입니다.

코드

#include <iostream>
#include <cstring>
#include <deque>
using namespace std;

bool maze[101][101];
int N, M, cnt[101][101];
constexpr int d[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

bool isValid(int y, int x) {
	return (0 < y && y <= N && 0 < x && x <= M);
}

int solve() {
	deque<pair<int, int>> dq;
	dq.push_front({1, 1});
	cnt[1][1] = 0;
	while (!dq.empty()) {
		int cy = dq.front().first, cx = dq.front().second;
		dq.pop_front();
		// 무조건 cnt가 작은 칸을 먼저 탐색하게 되므로,
		// 가장 먼저 (N, M)에 도달할 때 가장 벽을 적게 부수고 도착한다.
		if (cy == N && cx == M) break;
		for (int i = 0; i < 4; ++i) {
			int ny = cy + d[i][0], nx = cx + d[i][1];
			if (isValid(ny, nx) && cnt[ny][nx] == -1) {
				if (maze[ny][nx]) cnt[ny][nx] = cnt[cy][cx] + 1, dq.push_back({ny, nx});
				else cnt[ny][nx] = cnt[cy][cx], dq.push_front({ny, nx});
			}
		}
	}
	return cnt[N][M];
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> M >> N;
	string line;
	for (int y = 1; y <= N; ++y) {
		cin >> line;
		for (int x = 1; x <= M; ++x)
			maze[y][x] = line[x - 1] == '1' ? true : false;
	}
	memset(cnt, -1, sizeof(cnt));
	cout << solve();
}

결과