[백준][C++]2178번 미로 탐색

문제

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

2178번: 미로 탐색

 

 

풀이

• 완전 탐색을 진행하며 몇 번째 깊이에서 원하는 값을 찾을 수 있는지를 구하는 것과 동일

  ⇒ BFS를 사용해 최초로 도달했을 때 깊이를 출력

• BFS는 해당 깊이에서 갈 수 있는 노드 탐색을 마친 후 다음 깊이로 넘어가기 때문에 DFS보다 BFS가 적합하다. 

 

DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색) 알고리즘

DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색) 알고리즘

 

 

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void BFS();
static int N, M;
static vector<vector<int>> maze;
static vector<int> dx = {0, 0, -1, 1};
static vector<int> dy = {-1, 1, 0, 0};
static queue<pair<int, int>> myqueue;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  cin >> N >> M;

  maze.resize(N, vector<int>(M, 0));
  for(int i = 0; i < N; i++)
  {
    string str; 
    cin >> str;

    for(int j = 0; j < M; j++)
    {
      maze[i][j] = str[j] - '0';
    }
  }

  myqueue.push(make_pair(0, 0));
  maze[0][0] = 2;
  BFS();
  
  cout << maze[N - 1][M - 1] - 1;

  return 0;
}

void BFS()
{
  while(!myqueue.empty())
  {
    pair<int, int> now = myqueue.front();
    myqueue.pop();
    int x = now.first;
    int y = now.second;
    
    for(int i = 0; i < 4; i++)
    {
      int next_x = x + dx[i];
      int next_y = y + dy[i];
      if(next_x >= 0 && next_x < N && next_y >= 0 && next_y < M)	// 좌표 유효성 검사
      {
        if(maze[next_x][next_y] == 1)	// 미방문 노드 검사
        {
          maze[next_x][next_y] = maze[x][y] + 1;	// 깊이 업데이트
          myqueue.push(make_pair(next_x, next_y));
        }
      }
    }
  }

}