[Alogorithm] 백준 2178번 미로탐색 - BFS

문제

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

 

---

풀이 

• 처음에는 어렵게 생각했는데 토마토와 같이 배열의 값을 1씩 더해주면서 출구인 [N][M]의 값을 출력하면 되는 문제였다
• 문제와는 다르게 풀이에서는 지나갈 수 있는 길은 0, 벽은 -1로 값을 배열에 넣어 풀었다
• 새로 탐색하는 값을 queue에 push로 넣어줄 때 visit도 같이 체크해줘야지 메모리 초과가 나지 않는다 (이걸 몰라서 고치려고 한참 찾았다)
• 또 bfs 함수 내부에 내용을 작성할 때 if문의 조건들을 &&(and)로 연결해주고 안에 실행부를 넣는 것 보다 ||(or)로 조건들을 나열한 후 하나라도 만족했을 때 반복문을 빠져나가게 하는 것이 나중에 조건이 늘어날 때 훨씬 안전하다

코드

#include <queue>
using namespace std;
#include <cstdio>

int n;
int m;
int map[100][100] = {0,};
int visit[100][100] = {0,};
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};

// 구조체 
struct p {
  int x;
  int y;
};

queue <p> q;

void bfs(){
  p p1;
  p1.x = 0;
  p1.y = 0;
  q.push(p1); // 시작 위치를 queue에 넣어줌
  visit[0][0] = 1;

  while(!q.empty()){
    int now_x = q.front().x;
    int now_y = q.front().y;
    q.pop();

    for(int i=0; i<4; i++){
      int next_x = now_x + dx[i];
      int next_y = now_y + dy[i];

      if(next_x>=n || next_y>=m || next_x<0 || next_y<0 || visit[next_x][next_y]==1 || map[next_x][next_y]==-1) continue;
      
      p1.x = next_x;
      p1.y = next_y;
      q.push(p1);
      visit[next_x][next_y] = 1;
      map[next_x][next_y] = map[now_x][now_y]+1;

    }
  }
}

int main() {
  scanf("%d %d", &n, &m);

  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      scanf("%1d", &map[i][j]);
      if(map[i][j]==0) map[i][j]=-1;
      if(map[i][j]==1) map[i][j]=0;
    }
  }
  bfs();
  
  printf("%d", map[n-1][m-1]+1); // 출구의 배열값을 출력
}