문제 출처

1. 문제설명

  • 빈방 또는 벽으로 이루어진 미로가 있다.
  • 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다.

  • 현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지

  • 문제 분류
    • Graph, Dijkstra, 0-1 BFS


2. 알고리즘 설계

  • 다익스트라 또는 0-1 BFS로 풀이할 수 있다.
  • 이 문제의 경우 모든 케이스에 대해 0-1 BFS가 효율적이다.
  • 빈 방은 가중치 0, 벽은 1로 설정하고, 최단 경로를 찾아주면 된다.
    • 빈 방으로 이동할 때는 push_front(), 벽으로 이동할 때는 push_back()


3. 전체 코드

#include <bits/stdc++.h>
using namespace std;
using ti3 = tuple<int,int,int>;

const int SZ = 101;
const int dy[] = {-1,1,0,0};
const int dx[] = {0,0,-1,1};
char board[SZ][SZ];
bool vis[SZ][SZ];
int n, m, ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> m >> n;
	for(int i=0; i<n; i++)
		for(int j=0; j<m; j++)
			cin >> board[i][j];

	deque<ti3> dq;
	dq.push_front({0,0,0});
	vis[0][0] = true;

	int y, x, c;
	while(!dq.empty()) {
		auto [y, x, c] = dq.front();
		dq.pop_front();

		if(y == n-1 && x == m-1) {
			ans = c;
			break;
		}

		for(int dir=0; dir<4; dir++) {
			int ny = y + dy[dir];
			int nx = x + dx[dir];

			if(ny < 0 || nx < 0 || ny >= n || nx >=m) continue;
			if(!vis[ny][nx]) {
				if(board[ny][nx] == '0') dq.push_front({ny, nx, c});
				else dq.push_back({ny, nx, c+1});
				vis[ny][nx] = true;
			}
		}
	}

	cout << ans;

	return 0;
}