이런 유형의 문제들은 조금 더 빠르게 풀이를 떠올리고 슥삭하는 연습이 필요한 것 같다.
문제 요약
벽이 존재하는 미로가 주어지고 (1, 1) 위치에서 (N, M) 위치까지 간다고 할 때, 부숴야 하는 최소 벽의 개수를 구하는 문제
풀이
- Sequence
- 현재 큐에 존재하는 벽들을 부순다. (벽을 나타내는 1을 0으로 바꾼다.)
- DFS를 통해 벽이 없는 방에 대해 모두 탐색한다.
- 탐색하면서 벽을 만났을 때, 큐에 삽입하고 탐색 종료
처음 시작을 제외하고 위의 시퀀스를 한 번 반복하는 것을 벽을 하나씩 부순다고 가정한다. 그러면서 (N, M) 위치에 방문 체크가 되었다면 시퀀스를 종료하고 그동안 부순 벽의 개수가 정답이다.
코드
#include<iostream>
#include<queue>
using namespace std;
int N, M, ans, dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 };
char m[100][101];
bool v[100][100];
queue<pair<int, int>> q;
void dfs(int x, int y) {
if (0 > x || x >= M || 0 > y || y >= N) return;
if (m[y][x] == '1') {
q.push({ x,y });
return;
}
if (v[y][x]) return;
v[y][x] = 1;
for (int i = 0; i < 4; i++) dfs(x + dx[i], y + dy[i]);
}
int main() {
scanf("%d %d", &M, &N);
for (int i = 0; i < N; i++) scanf("%s", m[i]);
q.push({ 0,0 });
while (1) {
int t = q.size();
while (t--) {
int x = q.front().first, y = q.front().second;
q.pop();
m[y][x] = '0';
dfs(x, y);
if (v[N - 1][M - 1]) {
printf("%d", ans);
return 0;
}
}
ans++;
}
}