[백준] 2178번 미로 탐색 (C++) - BFS

문제

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

코드

#include <iostream>
#include <string>
#include <queue>

using namespace std;

int n, m;
int maze[101][101];
int isVisited[101][101] = {false, };
int dist[101][101];
queue<pair<int, int>> q;

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1 };

void bfs(int y, int x){
  q.push(make_pair(y, x));
  isVisited[y][x] = true;
  dist[y][x] = 1;
  while(!(q.empty())){
    y = q.front().first;
    x = q.front().second;
    q.pop();
    for(int i=0; i<4; i++){
      int nx = x+dx[i];
      int ny = y+dy[i];
      if (1 <= ny && ny <= n && 1 <= nx && nx <= m && maze[ny][nx] && !(isVisited[ny][nx])){
        q.push(make_pair(ny, nx));
        isVisited[ny][nx] = true;
        dist[ny][nx] = dist[y][x] + 1;
      } 
    }
  }
}

int main(){
  cin >> n >> m;
  for(int i=1; i<=n; i++){
    string r;
    cin >> r;
    
    for(int j=1; j<=m; j++){
      maze[i][j] = r[j-1]-'0';
    }
  }

  bfs(1, 1);

  cout << dist[n][m];
  return 0;
}

정리

처음에는 dfs로 문제를 접근하고 풀려했으나 정확한 이유는 모르겠으나 문제가 풀리지 않았다.

아직까지도 dfs와 bfs의 차이에 대해 정확히 알지 못하는 것 같다.

 

인터넷에 검색해보니 최단거리문제를 풀 때는 bfs가 좋다고 한다.

그 이유는 bfs의 경우 최단거리를 찾자마자 종료할 수 있고 dfs의 경우는 모든 경로를 탐색해야 하기 때문이라 한다.

 

dfs, bfs문제를 더 풀어봐야겠다.

참조

https://wooono.tistory.com/410

https://tooo1.tistory.com/163

https://www.acmicpc.net/board/view/27666