[2178] 미로 탐색 (C++)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 101

using namespace std;

int maze[MAX][MAX];
int visited[MAX][MAX];
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int N, M;

int BFS(int x, int y);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> M;
    string s;

    for (int i = 0; i < N; i++) {
        cin >> s;
        for (int j = 0; j < M; j++)
            maze[i][j] = s[j] - '0';
    }

    cout << BFS(0, 0) << endl;

    return 0;
}

int BFS(int x, int y) {
    queue<pair<int, int>> q;
    q.push({ x, y });
    visited[x][y] = 1;

    while (!q.empty()) {
        int tmp_x = q.front().first;
        int tmp_y = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int new_x = tmp_x + dx[i];
            int new_y = tmp_y + dy[i];

            if (new_x < 0 || new_x >= N || new_y < 0 || new_y >= M) continue;
            if (maze[new_x][new_y] == 0) continue;
            if (visited[new_x][new_y] != 0) continue;

            visited[new_x][new_y] = visited[tmp_x][tmp_y] + 1;
            q.push({ new_x, new_y });
        }
    }

    return visited[N - 1][M - 1];
}

 

1. 미로를 담을 배열과 방문 횟수를 기록할 배열을 생성

2. 상 하 좌 우를 나타낼 dx, dy를 생성

3. BFS를 사용, 좌표값이 미로 밖을 나타내거나 / 값이 0 이거나 / 방문 횟수가 0이 아니라면 해당 위치로 이동하지 않음

4. 다음 위치로 이동한 후 방문 횟수를 증가시킴

5. 도착 위치의 방문 횟수 값을 반환하여 출력