728x90
#include <cstdio>
#include <queue>
using namespace std;
struct Pos {
int x, y, b;
};
queue<Pos> q;
char a[1001][1001];
int dist[1001][1001][2];
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
int main() {
int n, m;
scanf("%d %d", &n, &m);
for (int i=0; i<n; ++i){
scanf("%s", a[i]);
}
q.push({0, 0, 0});
dist[0][0][0] = 1;
while(!q.empty()){
int x = q.front().x, y = q.front().y, broken = q.front().b;
q.pop();
if (x == n-1 && y == m-1) {
printf("%d\n", dist[x][y][broken]);
return 0;
}
for (int i=0; i<4; ++i){
int nx = x + dx[i];
int ny = y + dy[i];
if (0 <= nx && nx < n && 0 <= ny && ny < m && dist[nx][ny][broken] == 0){
if (a[nx][ny] == '1' && broken == 0){
dist[nx][ny][1] = dist[x][y][broken] + 1;
q.push({nx, ny, 1});
}
if (a[nx][ny] == '0'){
dist[nx][ny][broken] = dist[x][y][broken] + 1;
q.push({nx, ny, broken});
}
}
}
}
puts("-1");
return 0;
}
현재까지 벽을 부수었는가? 의 여부를 큐에 같이 넣어주어야 풀리는 문제였다.
bfs는 큐에 어떤 것을 넣어주느냐에 따라 탐색 순서가 달라지는데,
1) 벽을 부수고 가는 경우와
2) 벽을 부수지 않고 가는 경우
를 모두 너비 우선 탐색하도록 하였다.
특히, 벽은 1번만 부술 수 있으므로, "지금까지 벽을 부수었던 적이 있는가" 를 broken 변수에 저장하여,
다음 스텝에서 그 정보를 이용해 1), 2)를 가지쳐 나가도록 하였다.
728x90
'알고리즘, 자료구조 > 알고리즘' 카테고리의 다른 글
[백준] N과 M (2) - 조합 (0) | 2019.09.19 |
---|---|
[백준] 15649 N과 M (1) - 순열 (2) | 2019.09.19 |
[백준] 1694 숨바꼭질 (0) | 2019.09.12 |
[이진탐색] 1920 수 찾기, Binary search (0) | 2019.08.29 |
[Deque] 5430 AC (백준) (0) | 2019.08.28 |
댓글