C++로 풀어보는 미로 문제: BFS 알고리즘 완벽 가이드

문제 설명

미로 안에는 빈 공간과 벽이 있고, 그 사이에 공 하나가 놓여 있다고 가정해 보겠습니다. 공은 상·하·좌·우 어느 방향으로든 굴러가며 빈 경로를 따라 이동할 수 있지만, 벽에 부딪히기 전까지는 절대 멈추지 않습니다. 공이 한 번 멈춘 이후에만 다음 방향을 다시 선택할 수 있습니다.

공의 시작 위치, 목적지, 그리고 미로 정보가 주어졌을 때 우리가 확인해야 할 것은 공이 목적지 위에서 멈출 수 있는지입니다. 미로는 2차원 배열로 표현되며, 1은 벽, 0은 빈 공간을 의미합니다. 미로의 테두리는 모두 벽으로 둘러싸여 있고, 시작점과 도착점의 좌표는 행(row)과 열(column) 인덱스로 주어집니다.

입력 예시

예를 들어 다음과 같은 2차원 배열 형태의 미로가 입력으로 주어진다고 해 보겠습니다.

이때 시작 위치는 (0, 4), 목적지는 (4, 4)입니다. 출력 결과는 true이며, 실제로 공이 왼쪽 → 아래 → 오른쪽 순서로 굴러가면 목적지에서 정확히 멈출 수 있습니다.

해결 접근 방법

이 문제는 너비 우선 탐색(BFS)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 로직은 다음과 같습니다.

1. 초기화: 시작 위치를 큐(queue)에 삽입하고, 해당 좌표를 방문 완료 집합(set)에 기록합니다.
2. 목적지 검사: 큐에서 현재 위치를 꺼냈을 때 그 좌표가 목적지라면 즉시 true를 반환합니다.
3. 네 방향 굴리기: 상·하·좌·우 각 방향으로 공을 굴려, 벽이나 배열의 경계에 닿아 멈추게 되는 최종 지점을 계산합니다.
4. 방문 처리: 계산된 지점이 아직 방문되지 않았다면 방문 표시를 하고 큐에 추가합니다.
5. 반복 종료: 큐가 모두 비워질 때까지 목적지에 도달하지 못했다면 false를 반환합니다.

C++ 구현 코드

아래 예제 코드를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool hasPath(vector<vector<int>>& grid, vector<int>& start, vector<int>& destination) {
      int n = grid.size();
      int m = grid[0].size();
      queue<vector<int>> q;
      q.push(start);
      set<vector<int>> visited;
      visited.insert(start);
      while (!q.empty()) {
         vector<int> curr = q.front();
         q.pop();
         int x = curr[0];
         int y = curr[1];
         if (destination[0] == x && destination[1] == y)
            return true;
         int i = x;
         while (i + 1 < n && !grid[i + 1][y])
            i++;
         if (!visited.count({ i, y })) {
            visited.insert({ i, y });
            q.push({ i, y });
         }
         i = x;
         while (i - 1 >= 0 && !grid[i - 1][y])
            i--;
         if (!visited.count({ i, y })) {
            visited.insert({ i, y });
            q.push({ i, y });
         }
         i = y;
         while (i + 1 < m && !grid[x][i + 1])
            i++;
         if (!visited.count({ x, i })) {
            visited.insert({ x, i });
            q.push({ x, i });
         }
         i = y;
         while (i - 1 >= 0 && !grid[x][i - 1])
            i--;
         if (!visited.count({ x, i })) {
            visited.insert({ x, i });
            q.push({ x, i });
         }
      }
      return false;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,0,1,0,0},{0,0,0,0,0},{0,0,0,1,0},{1,1,0,1,1},{0,0,0,0,0}};
   vector<int> v1 = {0,4}, v2 = {4,4};
   cout << (ob.hasPath(v, v1, v2));
}

실행 결과

입력:

{{0,0,1,0,0},{0,0,0,0,0},{0,0,0,1,0},{1,1,0,1,1},{0,0,0,0,0}}, {0,4}, {4,4}

출력:

1

출력값 1(true)은 공이 목적지 (4, 4)에서 멈출 수 있음을 의미합니다.

복잡도 분석

시간 복잡도는 O(m × n × max(m, n))입니다. 각 칸은 최대 한 번씩 큐에서 처리되며, 한 번 처리할 때 한 방향으로 최대 m칸 또는 n칸까지 굴러갈 수 있기 때문입니다. 공간 복잡도는 방문 집합과 큐 저장을 위해 O(m × n)입니다.