백준) 2178 미로 탐색

2178. 미로 탐색

https://www.acmicpc.net/problem/2178

1. 접근

탐색은 BFS나 DFS로 조질 수 있다. 하지만 이동을 최소로 해야하기 때문에 BFS로 조져야 한다.

2. 풀이

이동의 횟수도 알아야 하기 때문에 큐질의 레벨을 기억해야 한다.

따라서 현재 레벨만큼 큐질을 하는 bfs질을 쓰자.

만약 (1, 1)에서 이동 할 수 있는 칸이 두 개 라면 다음 레벨은 두 칸이 저장될 것이다.

다음 레벨에서 큐질을 할 때면 두 칸에서 또 진행할 수 있는 칸들이 큐에 들어간다.

3. 코드

#include <stdio.h>
#include <queue>
using namespace std;
 
struct col {
    int x, y;
};
 
char buf[101];
int map[100][100];
int dir[4][2] = { { -1,0 },{ 1,0 },{ 0,-1 },{ 0,1 } };
int a, b;
 
int bfs() {
    queue<col> q;
    q.push({ 0, 0 });
 
    int cnt = 2;
 
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; ++i) {
            int x = q.front().x;
            int y = q.front().y;
            q.pop();
 
            if (map[x][y] != 1)
                continue;
            map[x][y] = cnt;
 
            if (x == a - 1 && y == b - 1)
                return cnt;
 
            for (int j = 0; j < 4; ++j) {
                int xx = x + dir[j][0];
                int yy = y + dir[j][1];
 
                if (xx < 0 || xx >= a || yy < 0 || yy >= b)
                    continue;
                if (map[xx][yy] != 1)
                    continue;
 
                q.push({ xx,yy });
            }
        }
        cnt++;
    }
    return cnt;
}
 
int main() {
    scanf("%d %d", &a, &b);
    for (int i = 0; i < a; ++i) {
        scanf("%s", buf);
        for (int j = 0; j < b; ++j)
            map[i][j] = buf[j] - '0';
    }
 
    printf("%d", bfs() - 1);
 
    return 0;
}

bfs 도중에 재방문을 막는 visit 처리는 따로 visit[][] 배열을 쓰지 않아도, 기존 맵의 정보를 고쳐가면서도 할 수 있었다.