[BOJ / C++] #2178 미로 탐색

문제풀이

N,M까지의 최단 거리를 구하는 것이므로, BFS를 이용한다.

1. 붙어있는 수 저장
   • string으로 받은 후
   • M번 for문을 돌며 string.at(i)로 자르기
   • 잘라진 char-48을 이용해 아스키 코드 숫자로 변경
2. 최단거리, BFS
   • int map[MAX][MAX] : 입력 배열
   • bool visited[MAX][MAX] : 방문 했는지
   • int length[MAX][MAX] : bfs 최단 거리 저장
   • int dr[4]={-1,0,1,0}, int dc[4]{0,1,0,-1} : 방향 벡터

코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define MAX 101

int N,M;
int map[MAX][MAX];
bool visited[MAX][MAX];
int length[MAX][MAX]; //이동거리 저장
//상우하좌
int dr[4]={-1,0,1,0};
int dc[4]={0,1,0,-1};

void bfs(int r, int c){

    queue<pair<int,int>> q;
    q.push(make_pair(r,c));
    length[r][c]=1;
    visited[r][c]=true;

    while(!q.empty()){
        int cr=q.front().first;
        int cc=q.front().second;
        q.pop();

        for(int i=0;i<4;i++){
            int nr=cr+dr[i];
            int nc=cc+dc[i];

            if(nr>N||nr<1||nc>M||nc<1||map[nr][nc]==0||visited[nr][nc]) continue;

            length[nr][nc]=length[cr][cc]+1;
            q.push(make_pair(nr,nc));
            visited[nr][nc]=true;
        }

    }


}

int main(){

    cin>>N>>M;
    for(int i=1;i<=N;i++){
        string str;
        cin>>str;
        for(int j=1;j<=M;j++){
            int a=(int)str.at(j-1)-48;
            map[i][j]=a;
        }
    }

    bfs(1,1);

    cout<<length[N][M]<<"\n";
}```