[BOJ/백준 2178][C++] 미로 탐색

문제

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

백준 2178

 

문제 내용

N*M크기의 미로 배열이 주어지고, (1,1)에서 (N, M)까지 이동할 때 지나가게 되는 최소의 칸 수를 구하면 되는 문제이다.

1은 이동할 수 있는 칸이고 0은 벽이며, 서로 인접한 칸으로만 이동할 수 있다.

 

문제 풀이

bfs를 활용하여 문제를 풀면 되는데, 방문 여부를 bool 값으로 저장하지 말고 거리를 저장하면 된다. 

이때 주의할 점은 입력이 공백 없이 주어진다는 점이다.

 

코드

#include <iostream>
#include <queue>
using namespace std;

int arr[101][101];
int dist[101][101];
int n, m;

int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, 1, -1};

int bfs() {
    queue<pair<int, int>> q;

    q.push({1, 1});
    dist[1][1] = 1;

    while (!q.empty()) {
        pair<int, int> p = q.front();
        q.pop();

        for (int i = 0; i < 4; i++) {

            int nr = p.first + dr[i];
            int nc = p.second + dc[i];

            // 인덱스 체크 && 이동할 수 있는 칸 && 아직 방문 안 했을 경우
            if (nr >= 1 && nr <= n && nc >= 1 && nc <= m && arr[nr][nc] == 1 && dist[nr][nc] == 0) {
                q.push({nr, nc});
                dist[nr][nc] = dist[p.first][p.second] + 1; // 거리 저장
            }
        }
    }

    return dist[n][m];
}

int main() {
    cin >> n >> m;
    string str;
    for (int i = 1; i <= n; i++) {
        cin >> str;

        for (int j = 1; j <= m; j++) {
            arr[i][j] = (str[j - 1] - '0');
        }
    }

    cout << bfs();
}