[알고리즘 19.1.9] BFS - 목수의 미로 탈출

문제

---

아래와 같이 이동할 수 있는 길, 그리고 이동할 수 없는 벽으로 이루어진 크기 N x M 의 지도가 주어진다. 이 때, (N-1, 0) 에서 출발하여 (0, M-1) 까지 도착하는 최단거리를 찾으려 한다. 그런데 목수는 도끼 하나를 갖고 있으며, 이 도끼를 이용하여 벽을 깨부술 수 있다. 하지만 이 도끼는 내구성이 그렇게 좋지 않기 때문에, 벽을 최대 1개밖에 깰 수 없다. 목수가 출발점에서 도착점까지 이동하기 위한 최단거리를 출력하는 프로그램을 작성하시오. 물론, 벽은 최대 1개까지 깰 수 있다. 아래 예제의 경우 ‘X’ 로 표시된 벽을 깰 경우 거리 18만에 출발점에서 도착점으로 이동할 수 있다.

 

입력

---

첫째 줄에 지도의 세로 길이 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

예제 출력

18

 

예제 입력

10 10
0 0 0 0 0 0 1 1 0 0
0 1 1 1 0 0 1 1 1 0
0 1 1 1 0 0 1 1 1 0
0 0 0 0 0 0 0 1 1 0
0 0 1 1 1 1 0 1 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 1 0 0
0 0 0 0 0 1 1 1 1 1
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;
 
//거꾸로 가는 BFS();
int checkR[MAX][MAX];
 
//큐에 넣을 좌표 구조체
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){
      now.n = nx;
      now.m = ny;
      q.push(now);
      check[nx][ny]=temp+1;
    }
  }
  if(!q.empty() && flag==0) BFS();
}
 
void BFS_R(){
  if(q.empty() && flag !=0) return;
  
  coor now = q.front();
  q.pop();
  
  int a = now.n;
  int b = now.m;
  
   //check 숫자 저장
  int temp = checkR[a][b];
  
  int nx, ny;
  for(int i=0; i<4; i++){
    nx = a + dx[i];
    ny = b + dy[i];
    if(inside(nx, ny) && checkR[nx][ny]==0 && arr[nx][ny]!=1){
      now.n = nx;
      now.m = ny;
      q.push(now);
      checkR[nx][ny]=temp+1;
    }
  }
  if(!q.empty() && flag==0) BFS_R();
  
}
 
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();
  
  checkR[0][m-1]=1;
  q.push(coor(0,m-1));
  flag = 0;
  BFS_R();
  
  //입력받은 arr을 순회하면서 벽이 있으면
  //벽 주변의 값들과 덧셈을 하고,
  //가장 최소값을 출력하면 됌.
  int min = 987987987;
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      //해당 수가 벽일 경우.
      int sm=987987987, em=987987987;
      if(arr[i][j]==1){
        //스타트에서부터 시작하는 bfs의 최솟값과
        //엔드에서부터 시작하는 bfs의 최솟값을 더하면 됌.
        int nx, ny;
        for(int q=0; q<4; q++){
          nx = i + dx[q];
          ny = j + dy[q];
          if(inside(nx,ny)){
            if(sm>check[nx][ny] && check[nx][ny]!=0) sm = check[nx][ny];
            if(em>checkR[nx][ny] && checkR[nx][ny]!=0) em = checkR[nx][ny];
            if(min>sm+em) min = sm+em;
          }
        }
        
      }
    }
  }
  
  cout<<min<<endl;
  
  return 0;
}