백준 2178 미로탐색 / C++

문제 : 링크텍스트

풀이 point

bfs를 활용한 탐색
bfs를 활용하여 탐색을 진행하면서 새로운 곳을 탐색할 때는 이전 길 걸음 수 + 1을 하여 거리 값을 갱신한다.
도착 위치는 항상 N-1, M-1이다.
visit 배열을 사용할 필요는 없다.

풀이 순서

1. bfs 진행
2. N-1, M-1 거리 값을 출력

코드

#include <iostream>
#include <vector>
#include <queue>

#define x first
#define y second

std::queue<std::pair<int, int>> Q;
std::vector<int> dx = {-1, 0, 1, 0};
std::vector<int> dy = {0, 1, 0, -1};

int N, M;
int grid[100][100];
int dist[100][100];

//백준 2178, 미로 탐색
void testprint(){
        std::cout << "--------------------------------------------" << '\n';
        for(int i{0}; i<N; ++i){
            for(int j{0}; j<M; ++j){
                std::cout << grid[i][j] << ' ';
            }
            std::cout << '\n';
        }
}

void bfs(int i, int j){
    Q.push({0, 0});
    grid[0][0] = 0;
    while(!Q.empty()){
        auto curr = Q.front(); Q.pop();
        for(int k{0}; k<4; ++k){
            int nx = curr.x + dx[k];
            int ny = curr.y + dy[k];
            if(nx >= N || nx < 0 || ny < 0 || ny >= M) continue;
            if(grid[nx][ny] == 0) continue;
            Q.push({nx, ny});
            dist[nx][ny] = dist[curr.x][curr.y] + 1;
            grid[nx][ny] = 0;
        }
    }
}


int main(){
    
    std::cin >> N >> M;
    for(int i{0}; i<N; ++i){
        std::string row;
        std::cin >> row;
        for(int j{0}; j<M; ++j){
            grid[i][j] = row[j]-'0';
        }
    }

    bfs(0, 0);
    std::cout << dist[N-1][M-1] + 1;
    
    //testprint();
    return 0;
}