[백준 2178번] [BFS] 미로 탐색

Approach

DFS가 아니라 BFS로 해야한다. DFS로 하게 되면 모든 가능한 케이스를 모두 조사해보아야 하는데, 그 경우는 $4^{NM}$이므로 시간초과가 난다. 추가적으로 큐에 여러번 들어갈 수 있는 가능성을 없애기 위해서 큐에 넣자마자 방문처리를 해줘야 한다. 이 부분때문에 처음에 메모리초과를 받았다.

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0);

using namespace std;
typedef pair<int, int> pii;

char r[100][100];
int visited[100][100];

int move_x[4] = {-1, 1, 0, 0};
int move_y[4] = {0, 0, -1, 1};

int main(void){
    fastio;
    memset(visited, 0, sizeof(visited));
    int n, m;
    cin >> n >> m;

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> r[i][j];
        }
    }

    queue<pii> q;
    int result = 1;
    q.push(make_pair(0, 0));
    visited[0][0] = 1;
    while(true){
        int q_size = q.size();
        for(int i = 0; i < q_size; i++){
            pii cur = q.front();
            if(cur == make_pair(n - 1, m - 1)){
                cout << result << "\n";
                return 0;
            }
            visited[cur.first][cur.second] = 1;
            q.pop();
            for(int j = 0; j < 4; j++){
                int x = cur.first + move_x[j];
                int y = cur.second + move_y[j];
                if(x < 0 || x >= n || y < 0 || y >= m) continue;
                if(!visited[x][y] && r[x][y] == '1'){
                    q.push(make_pair(x, y));
                    visited[x][y] = 1;
                }
            }
        }
        result++;
    }
}