[알고리즘 19.1.5] BFS - 미로찾기

문제

---

아래와 같이 이동할 수 있는 길, 그리고 이동할 수 없는 벽으로 이루어진 크기 N x M 의 지도가 주어진다. 이 때, (N-1, 0) 에서 출발하여 (0, M-1) 까지 도착하는 최단거리를 출력하는 프로그램을 작성하시오. 아래 그림에 대하여 S에서 E까지 가는 최단거리는 22이다.

 

입력

---

첫째 줄에 지도의 세로 길이 N과 지도의 가로 길이 M이 주어진다. ( 1 ≤ N, M ≤ 1,000 ) 둘째 줄부터 지도의 정보가 주어진다. 0은 이동할 수 있는 부분, 1은 이동할 수 없는 부분을 나타낸다.

 

출력

---

(N-1, 0) 에서 출발하여 (0, M-1) 까지 이동하는 데 필요한 최단거리를 출력한다.

 

예제 입력

10 10
0 0 0 0 0 0 1 1 0 0
0 1 1 1 0 0 1 0 1 0
0 1 1 1 0 0 1 0 1 0
0 0 0 0 0 0 0 0 1 0
0 0 1 1 1 1 0 0 1 0
0 0 0 0 0 0 1 1 0 0
0 0 1 1 1 0 1 1 0 0
0 0 1 1 1 0 0 0 0 0
0 0 0 0 0 1 1 1 0 0
0 0 0 0 0 0 0 1 0 0

예제 출력

22

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
 
//벽 배열, 확인 배열, 벽 크기 입력, 출발점, 도착점
const int MAX = 1005;
int arr[MAX][MAX];
int check[MAX][MAX];
int n, m;
 
//큐에 넣을 좌표 구조체
typedef struct coor{
  int n;
  int m;
  coor(){};
  coor(int _n, int _m) : n(_n), m(_m){};
}coor;
queue <coor> q;
 
//방문할 4공간 배열 - 방문순서 좌 하 상 우
int dx[4] = {0,-1,1,0};
int dy[4] = {1,0,0,-1};
 
//inside체크
bool inside(int a, int b){
  return (a>=0 && a<n) && (b>=0 && b<m);
}
 
//BFS 중지할 flag
int flag = 0;
 
//이동거리를 나타낼 변수
int cnt = 0;
 
//BFS
void BFS(){
  if(q.empty() && flag!=0) return;
  coor now = q.front();
  q.pop();
  
  int a,b;
  a = now.n;
  b = now.m;
  
  //check 숫자 저장
  int temp = check[a][b];
  
  int nx, ny;
  for(int i=0; i<4; i++){
    nx = a + dx[i];
    ny = b + dy[i];
    if(inside(nx, ny) && check[nx][ny]==0 && arr[nx][ny]!=1){
      if(nx==0 && ny ==m-1){
        flag = temp;
        return;
      }
      now.n = nx;
      now.m = ny;
      q.push(now);
      check[nx][ny]=temp+1;
      //cout<<nx<<","<<ny<<endl;
      
    }
  }
  if(!q.empty() && flag==0) BFS();
}
 
int main(){
  cin>>n>>m;
 
  
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      cin>>arr[i][j];
    }
  }
  
  check[n-1][0] = 1;
  q.push(coor(n-1,0));
  BFS();
  
  cout<<flag<<endl;
  /*
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      cout<<check[i][j]<<" ";
    }
    cout<<endl;
  }
  */
  
  return 0;
}