Info
Write UP
BFS에 익숙해지기 위해 관련 문제들을 모두 풀고 있어요.
M x N 크기에 이동할 수 있는 칸은 1로, 벽은 0으로 표시된 미로가 주어집니다.
우리는 (1, 1)에서 출발하여 (N, M)으로 갈 때 지나야 하는 최소 칸수를 구해야 해요.
시간제한은 1초이지만 경우의 수가 그리 많지 않기 때문에 완전탐색으로 풀면 될 것 같습니다.
(1, 1)부터 상하좌우 탐색을 해서 방문하지 않았고, 지도 상 1로 표시된 부분을 찾아 이동하면 되겠죠?
좌표를 찾았을 경우 어떻게 처리할 지 생각해볼게요.
DFS로 푼다면 길이 나뉘어졌을 때 한 쪽으로만 계속 들어갑니다. 그 곳이 막혀있는 길이면 다시 갈림길로 돌아와 다른 곳으로 나아가요.
물론 이렇게 풀어도 되겠지만 만약 하염없이 깊게 들어갔는데 막다른 길이면 재귀가 많이 호출되겠죠?
그래서 저는 안전하게 BFS로 풀었습니다.
큐에 현재 좌표를 넣고 방문 표시, pop 후 상하좌우 탐색을 해서 나아갈 수 있는 모든 좌표를 큐에 push ... 이걸 큐가 빌 때까지 반복하면 되겠네요.
방문 표시를 할 때 전 좌표에 들어있던 값 + 1을 해줬습니다. 어짜피 나아갈 길은 1로 표시되기 때문에 그 이후엔 2, 3, 4.. 이런 식으로 cnt처럼 쌓여요.
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
int map[101][101] = {0,};
int chk[101][101] = {0,};
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int N, M;
int bfs(int x, int y) {
queue<pair<int, int>> que;
que.push(pair<int, int>(x, y));
chk[y][x] = 1;
while (!que.empty()) {
int cx = que.front().first;
int cy = que.front().second;
que.pop();
if (cx == M - 1 && cy == N - 1) break;
for (int i = 0; i < 4; i++) {
int nx = cx + dx[i];
int ny = cy + dy[i];
if (map[ny][nx] == 1) {
if (nx >= 0 && nx < M && ny >= 0 && ny < N) {
if (chk[ny][nx] == 0) {
chk[ny][nx] = chk[cy][cx] + 1;
que.push(pair<int, int>(nx, ny));
}
}
}
}
}
return chk[N-1][M-1];
}
int main() {
scanf("%d %d", &N, &M);
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
scanf("%1d", &map[i][j]);
}
}
printf("%d\n", bfs(0, 0));
return 0;
}
WEB / Security