[백준 2178][C++] 미로탐색 (Silver 1)

[문제보기]

 2178. 미로탐색

2178번: 미로 탐색

 

[풀이과정]

이 문제는 완전 탐색 알고리즘에서 BFS 알고리즘을 사용하면 되는 문제이다.

 

bool check[][]를 통해 왔던 길이나 확인했던 길에 대해 방문 여부를 주어준다.

[소스코드]

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int n, m, ans = 987654321;
int map[100][100];
bool check[100][100];
pair<int, int> movdir[4] = {{1,0}, {-1,0}, {0, 1}, {0, -1}};

void bfs(int sy, int sx){
    queue<pair<int, int>> q;
    q.push(make_pair(sy, sx));
    check[sy][sx] = false;
    int cnt = 1;

    while(!q.empty()){
        int size = q.size();
        cnt++;
        
        for(int cur = 0; cur<size; cur++){
            int y = q.front().first;
            int x = q.front().second;
            q.pop();

            for(int i=0; i<4; i++){
                int nexty = y + movdir[i].first;
                int nextx = x + movdir[i].second;

                if(nexty == n-1 && nextx == m-1){
                    ans = cnt;
                    return;
                }

                if(nexty < 0 || n <= nexty || nextx < 0 || m <= nextx) continue;
                if(map[nexty][nextx] == 0) continue;

                if(check[nexty][nextx]){
                    check[nexty][nextx] = false;
                    q.push({nexty, nextx});
                }
            }
        }
    }
}

int main(){
    memset(check, true, sizeof(check));
    cin >> n >> m;
    for(int i=0; i<n; i++){
        string s;
        cin >> s;
        for(int j=0; j<m; j++){
            map[i][j] = s[j] - '0';
        }
    }

    
    bfs(0, 0);

    cout << ans;
}

 

[해결 과정 중 실수한 부분]