BOJ 2206 벽부수고 이동하기(BFS)
이 문제는 BFS로 해결할 수 있다.
이때 각 위치까지의 경로가 벽을 한번 부수고 왔을 수도, 아닐 수도 있기 때문에, 두 가지 방문 표시를 사용해야 한다.
•
visited[y][x][0] = (x, y) 위치까지의 경로에서 벽을 한 칸도 부수지 않았을 때의 방문 표시
•
visited[y][x][1] = (x, y) 위치까지의 경로에서 벽을 한 칸 부셨을 때의 방문 표시
node 구조체는 각 칸의 위치 정보와, depth(경로의 길이), flag(현재까지의 경로에서 벽을 부셨다면 1, 부수지 않았다면 0)으로 이루어져 있다.
Solution
1.
시작 위치의 정보 x = 0, y = 0, depth = 1, flag = 0 을 queue에 푸시한 후, 방문 표시 visited[0][0][0]을 한다.
2.
queue에서 원소를 pop한다.
3.
pop한 원소의 위치 정보가 map의 마지막 위치라면, 해당 원소의 depth(경로의 길이)를 반환한다.
4.
현재 위치에서 상하좌우 중 이동 가능한 다음 위치를 탐색한다.
4-1. 다음 위치의 원소가 1이고 아직 벽을 부수지 않았다면, 벽을 부셨다는 방문 표시 후, queue에 push 한다.
4-2. 다음 위치의 원소가 0이고 방문하지 않았다면, 방문 표시 후, queue에 push 한다.
5.
map의 마지막 위치 혹은 queue가 empty일 때까지 2~4 과정을 반복한다.
6.
만약 queue가 empty일 때까지 마지막 위치를 찾지 못했다면, 경로를 찾지 못한 것이므로, -1을 반환한다.
#include <iostream>
#include <queue>
#include <vector>
#define MAX 1001
using namespace std;
typedef struct node {
int x;
int y;
int depth; // 경로의 길이
int flag; // 현재까지의 경로에서 벽을 부셨다면 1, 부수지 않았다면 0
};
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
int N, M;
int map[MAX][MAX];
bool visited[MAX][MAX][2] = { false, };
int bfs() {
queue<node> q;
visited[0][0][0] = true;
q.push({ 0, 0, 1, false });
while (!q.empty()) {
node curr = q.front();
q.pop();
if (curr.x == M-1 && curr.y == N-1) {
return curr.depth;
} // pop한 원소의 위치 정보가 map의 마지막 위치라면, 해당 원소의 depth를 반환한다
for (int i = 0; i < 4; i++) {
int xx = curr.x + dx[i];
int yy = curr.y + dy[i];
if (xx < 0 || yy < 0 || xx >= M || yy >= N) continue;
if (map[yy][xx] == 1 && curr.flag == 0) {
// 다음 위치의 원소가 1이고, 아직 벽을 부수지 않았다면
visited[yy][xx][curr.flag+1] = true;
// 벽을 부셨다는 방문 표시 후,
q.push({ xx, yy, curr.depth+1, curr.flag+1 });
}
else if (map[yy][xx] == 0 && !visited[yy][xx][curr.flag]) {
// 다음 위치의 원소가 0이고, 방문하지 않았다면
visited[yy]xx][curr.flag] = true;
// 방문 표시 후,
q.push({ xx, yy, curr.depth+1, curr.flag });
}
}
}
return -1;
// 만약 queue가 empty일 때까지 마지막 위치를 찾지 못했다면, 경로를 찾지 못한 것이므로 -1을 반환
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
scanf("%d %d", &N, &M);
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
scanf("%1d", &map[i][j]);
}
}
cout << bfs();
return 0;
}
C++
복사