[BOJ] 백준 2178 미로 탐색

[BOJ] 백준 2178 미로 탐색

문제 링크 : https://www.acmicpc.net/problem/2178

이 문제는 BFS를 이용하여 갈 수 있는 모든 길을 탐색하되,

목적지까지 최단거리로 가야 하는 문제 입니다.

출발지는 1, 1 지역 입니다. 여기서부터 출발을 하는데 1.1에서 갈 수 있는 지역은

1, 2 와 2, 1 두군데 입니다. 따라서 이 두 지역에서 실시하는 BFS 루트들은, 같은 실행횟수를 가집니다(2번째 실행). 같은 방법으로 1,2 or 2,1 에서 실시하는 BFS 루트들은 같은 실행횟수를 가집니다(3번째 실행). 이방법으로 목적지까지 몇회째에 도착하는지 찾는 문제 입니다.

소스코드 : 

#include 
#include 
using namespace std;

// 갈수있는 4방위
struct Move{
 int x, y;
};
Move move[4] = { { -1,0 },{ 0,1 },{ 0,-1 },{ 1,0 } };

bool visited[102][102];
int v[102][102];
int check = 0;
int N, M;

// x, y좌표를 페어로 저장
queue> q;

void BFS(pair idx) {
 visited[idx.first][idx.second] = true;
 // 큐가 비워질때까지 루프.
    while (!q.empty()) {
        // 현재 큐의 사이즈만큼만 루프를 돈다.(이 루프 안에서 실행되는 것들은 같은 실행시간을 가짐)
  int size = q.size();
  while (size--) {
   int cur_x = q.front().first;
   int cur_y = q.front().second;
            // 목적지라면 탈출
   if (cur_x == N && cur_y == M) return;
   q.pop();
            // 갈수 있는 모든 방향을 큐에 넣는다.
   for (int i = 0; i < 4; i++) {
    if (!visited[cur_x + (::move[i].x)][cur_y + ::move[i].y] && v[cur_x + (::move[i].x)][cur_y + ::move[i].y] == 1) {
     visited[cur_x + (::move[i].x)][cur_y + ::move[i].y] = true;
     q.push({ cur_x + (::move[i].x) , cur_y + ::move[i].y });
    }
   }
  }
        // 사이즈만큼 돌은 후 횟수 올림.
  check++;
 }

}

int main() {

  cin >> N >> M; cin.ignore();
  
  for (int i = 1; i <= N; i++) {
   for (int j = 1; j <= M; j++) {
    scanf("%1d", &v[i][j]);
   }
  }
  q.push({1,1});
  check++;
  BFS(q.front());
  cout << check << endl;
}