[BaekJoon] 2178번 : 미로 탐색

• 이 글은 c++로 풀이를 작성하였습니다.

문제

 

예시

 

풀이

• BFS 특징 중 하나는 탐색하는 영역을 최소한의 거리로 탐색한다는 특징이 있습니다.
• 따라서 BFS 알고리즘으로 원하는 공간을 처음으로 탐색했던 시간이 최단거리 입니다.

#include<iostream>
#include<queue>
#include<utility>
#include<algorithm>
#include<string>
using namespace std;

int n,m;
int arr[100][100];
int dist[100][100];
int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};

bool inside(int y,int x){
    return 0<=y && y<n && 0<=x && x<m;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin>>n>>m;
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        for(int j=0;j<m;j++){
            arr[i][j] = s[j] - '0';
        }
    }
    
    queue<pair<int,int>> q;
    q.push({0,0});
    dist[0][0] = 1;
    
    while(!q.empty()){
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        
        for(int i=0;i<4;i++){
            int dy = y + dir[i][0];
            int dx = x + dir[i][1];
            
            if(inside(dy,dx) && arr[dy][dx] && dist[dy][dx] == 0){
                q.push({dy,dx});
                dist[dy][dx] = dist[y][x] + 1;
            }
        }
    }
    cout<<dist[n-1][m-1];
}

• 추가로 궁금한 점이나 수정할 부분이 있으면 댓글로 남겨주세요.