(C++) 백준 2178번 - 미로 탐색

문제 링크 : https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

풀이

BFS를 사용하여 풀이하였다. 다른 BFS 문제를 풀어보았다면 실버 1 문제라기엔 크게 어렵지 않은 문제이다.

오히려 공백없이 들어오는 숫자들을 어떻게 한 자리씩 입력받아 저장할지를 더 많이 고민하였다.

#include <iostream>
#include <queue>
#include <utility>
#define X first
#define Y second

using namespace std;

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int brd[500][500];
int dist[500][500];
queue<pair<int,int>> Q;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);  

    int n, m;
    cin >> n >> m;

    for(int i = 0; i < n; i++){ // 미로 저장
        string s;
        cin >> s;
        for(int j = 0; j < m; j++){
            brd[i][j] = s[j] - '0';
        }
    }

    Q.emplace(0, 0);
    dist[0][0] = 1;
    while(!Q.empty()){ // 거리 계산 시작
        int prev = dist[Q.front().X][Q.front().Y]; // 이전 거리 저장
        for(int i = 0; i < 4; i++){
            int x = Q.front().X;
            int y = Q.front().Y;
            x += dx[i];
            y += dy[i];
            if(x >= 0 && x < n && y >= 0 && y < m){ // 유효성 검사
                if(brd[x][y] == 1 && dist[x][y] == 0){ // 해당 칸의 값이 1이고, 거리 계산된 적이 없다면 거리 계산을 시작
                    Q.emplace(x, y); // 방문할 칸 큐에 저장
                    dist[x][y] = prev + 1; // 방문 표시
                }
            }
        }
        Q.pop();
    }
    cout << dist[n-1][m-1];
}