[백준] 미로탐색 2178번 (c++)

출처 : 2178번: 미로 탐색 (acmicpc.net)

2178번: 미로 탐색

풀이 방법

BFS문제로 1,1에서 시작하여 N, M까지의 최단 거리를 구하는 문제이다

que에서 pop을 한 뒤 이 좌표가 미로 좌표 내의 좌표인지 확인하고

그 좌표자리가 벽인지 길인지 확인한 후 길이면 이전 거리(dx, dy를 더 해주기 전)에 + 1을 해준후 배열에 저장하고 

자신 좌표를 que에 넣어 주는 방법으로 반복한다.

#include <bits/stdc++.h>

using namespace std;

int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
#define pii pair<int, int>
vector<string> board;
int visited[101][101];
int distance_map[101][101];
int N, M;
void BFS() {
    queue<pii> que;
    que.push(make_pair(0, 0));
    visited[0][0] = 1;
    while (!que.empty()) {
        int x, y;
        y = que.front().first;
        x = que.front().second;
        que.pop();
        for (int i = 0;i < 4;i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];
            if (nextX >= 0 && nextX < M && nextY >= 0 && nextY < N) {
                if (visited[nextY][nextX] == 0) {
                    if (board[nextY][nextX] == '1') {
                        distance_map[nextY][nextX] = distance_map[y][x] + 1;
                        que.push(make_pair(nextY, nextX));
                        visited[nextY][nextX] = 1;
                    }
                }
            }
        }

    }
}
int main() {
    cin >> N >> M;
    string str;
    memset(visited, 0, sizeof(visited));
    distance_map[0][0] = 1;
    for (int i = 0;i < N;i++) {
        cin >> str;
        board.push_back(str);
    }
    BFS();
    cout << distance_map[N-1][M-1];
    return 0;
}