[백준] 2178 미로탐색

미로에서 최단거리를 구하는 문제

BFS를 이용해 구할 수 있다

상하좌우 이므로 4방향 탐색을 해야한다!

dist[nx][ny]를 갈 수 있는 곳이라면 dist[x][y] +1이 된다!

소스코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int arr[111][111], dist[111][111];
bool check[111][111];
int n, m;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
 
int main() {
    scanf(" %d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf(" %1d", &arr[i][j]);
        }
    }
    queue<int> q;
    q.push(0);
    dist[0][0] = 1;
    while (!q.empty()) {
        int pos = q.front();
        q.pop();
 
        int x = pos / m;
        int y = pos%m;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                if (!check[nx][ny] && arr[nx][ny]) {
                    dist[nx][ny] = dist[x][y] + 1;
                    check[nx][ny] = true;
                    q.push(nx*m+ny);
                }
            }
        }
    }
    printf("%d\n", dist[n - 1][m - 1]);
}