(매일 BOJ) C++ 2178번 미로 탐색

이번 문제는 2178번 미로탐색이

문제 요약

N×M 크기의 미로가 주어질 때 미로는 0(벽), 1(길)로 이루어져 있고,
시작점 (1,1)에서 도착점 (N,M)까지 이동할 때 지나야 하는 최소 칸 수를 구하는 문제이다
이동은 상하좌우 네 방향만 가능하고 최단 거리를 구해야 하므로 DFS가 아니라 BFS를 써서 해결해야 하는 유형이다

 

아이디어 정리

1. BFS
   • 가까운 곳부터 차례대로 탐색하기 때문에 최단 거리에 적합
   • 큐(queue)를 사용하여 현재 칸에서 이동 가능한 칸을 차례로 넣고, 한 칸씩 꺼내면서 탐색한다
2. 거리 저장
   • 단순히 방문 여부만 체크하면 안 되고, 해당 칸까지 도달하는 최단 거리를 기록해야 한다
   • distance 배열을 따로 두어 (이전 칸 거리 + 1)로 갱신해야 함
3. 좌표 주의
   • 입력은 (1,1)에서 시작하는 것처럼 보이지만 실제 배열 인덱스는 0부터 시작하므로 (0,0)에서 시작해야 함
   • 도착지는 (N-1, M-1)

작성코드

#include <bits/stdc++.h>
using namespace std;

int fourway_x[4] = {1,-1,0,0};
int fourway_y[4] = {0,0,1,-1};
int N,M;
int BFS(int x, int y,vector<vector<int>> & graph);


int main (void){
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> N >> M; // N 세로, M 가로
    vector<vector<int>> graph(N,vector<int>(M,0));
    for(int i = 0; i < N; i++){
        string str;
        cin >> str;
        for(int j = 0; j < str.size(); j++){
            graph[i][j] = int(str[j] - '0');
        }
    }

    int count = BFS(0,0,graph);

    cout << count;

    return 0;
}

int BFS (int x, int y,vector<vector<int>> & graph){
    vector<vector<int>> distance (N,vector<int>(M,0));
    queue<pair<int,int>> q;

    q.push({x,y});
    distance [x][y] = 1;

    while(!q.empty()){
        pair<int,int> cur = q.front();
        int cur_x = cur.first;
        int cur_y = cur.second;
        q.pop();
        
       for(int i = 0; i < 4; i++){
            int nx = cur_x + fourway_x[i];
            int ny = cur_y + fourway_y[i];

            if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;

            if(distance[nx][ny] == 0 && graph[nx][ny] == 1 ){
                distance[nx][ny] = distance[cur_x][cur_y] + 1;
                q.push({nx,ny});    
            }
       } 
    }
    return distance[N-1][M-1];
}