Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ BFS와 비트마스크로 모든 키를 모으는 최단 경로 구현하기

문제 소개

격자(grid) 위에서 이동하며 모든 키를 수집하는 최단 경로를 찾는 문제입니다. 격자를 구성하는 기호는 다음과 같습니다.

  • . — 빈 칸
  • # — 벽(지나갈 수 없음)
  • @ — 시작 지점
  • a, b, ... — 키
  • A, B, ... — 자물쇠

시작 지점에서 출발해 한 번에 상·하·좌·우 네 방향으로 한 칸씩 이동할 수 있습니다. 격자 밖으로 나갈 수 없으며, 벽은 통과할 수 없습니다. 키가 놓인 칸을 지나가면 그 키를 자동으로 주워 담게 되고, 자물쇠가 있는 칸은 대응하는 키(자물쇠 A ↔ 키 a)를 이미 가지고 있을 때만 통과할 수 있습니다.

목표는 모든 키를 수집하는 데 필요한 최소 이동 횟수를 구하는 것이며, 불가능하다면 -1을 반환해야 합니다.

예를 들어 입력이 ["@.a.#", "###.#", "b.A.B"]일 때 정답은 8입니다.

풀이 아이디어: BFS + 비트마스크

일반적인 최단 경로 탐색과 이 문제의 결정적인 차이는 현재 보유한 키의 집합도 상태에 포함해야 한다는 점입니다. 같은 좌표라도 어떤 키를 들고 있느냐에 따라 앞으로 갈 수 있는 길이 달라지기 때문입니다.

이를 해결하기 위해 다음 전략을 사용합니다.

  • 보유한 키를 비트마스크(bitmask)로 표현합니다. 키 a는 0번 비트, 키 b는 1번 비트처럼 각 키를 한 비트에 대응시킵니다.
  • BFS(너비 우선 탐색)를 진행하되, 방문 처리를 (키 비트마스크, 행, 열) 세 요소의 조합으로 관리합니다.
  • 레벨 단위로 BFS를 수행하여, 모든 키를 모은 순간의 레벨 값이 곧 최소 이동 횟수가 됩니다.

알고리즘 동작 과정

  1. 행 개수 n, 열 개수 m을 구하고, '@'의 위치를 시작 상태로 저장합니다.
  2. 격자를 훑으며 존재하는 키의 개수 cnt를 계산합니다.
  3. 목표 비트마스크 req = (1 << cnt) - 1로 설정합니다. 하위 cnt개 비트가 모두 1인 값으로, "모든 키 보유" 상태를 의미합니다.
  4. 시작 상태를 큐에 넣고 방문 집합에 등록한 뒤, level을 0으로 초기화합니다.
  5. 큐가 빌 때까지 아래 과정을 반복합니다.
    • 현재 레벨에 있는 상태들을 모두 꺼내 확인합니다.
    • 꺼낸 상태의 키 비트마스크가 req와 같다면 지금까지의 level을 반환합니다.
    • 네 방향으로 이동을 시도하며 다음을 검사합니다.
      • 격자 범위를 벗어나거나 벽('#')이면 무시합니다.
      • 이동한 칸이 키(a~f)라면 OR 연산으로 해당 비트를 켭니다.
      • 이동한 칸이 자물쇠(A~F)라면 대응 비트가 켜져 있는지 검사하고, 키가 없으면 진행하지 않습니다.
      • 새 상태(키, nx, ny)가 아직 방문되지 않았다면 큐와 방문 집합에 추가합니다.
  6. 한 레벨의 탐색이 끝나면 level을 1 증가시킵니다.
  7. 큐가 소진될 때까지 목표 상태에 도달하지 못하면 -1을 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
class Solution {
   public:
   int shortestPathAllKeys(vector<string>& grid) {
      int n = grid.size();
      int m = grid[0].size();
      vector<int> start(3);
      int cnt = 0;
      for (int i = 0; i < n; i++) {
         for (int j = 0; j < m; j++) {
            if (grid[i][j] == '@') {
               start[1] = i;
               start[2] = j;
            }
            if (grid[i][j] >= 'a' && grid[i][j] <= 'f') {
               cnt = max(cnt, grid[i][j] - 'a' + 1);
            }
         }
      }
      set<vector<int> > visited;
      int req = (1 << cnt) - 1;
      queue<vector<int> > q;
      q.push(start);
      visited.insert(start);
      int level = 0;
      while (!q.empty()) {
         int sz = q.size();
         while (sz--) {
            vector<int> curr = q.front();
            q.pop();
            int key = curr[0];
            if (key == req)
            return level;
            int x = curr[1];
            int y = curr[2];
            int nx, ny;
            int prevKey = key;
            for (int i = 0; i < 4; i++) {
               nx = x + dir[i][0];
               ny = y + dir[i][1];
               key = prevKey;
               if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
                  if (grid[nx][ny] == '#')
                  continue;
                  if (grid[nx][ny] >= 'a' && grid[nx][ny] <=
                  'f') {
                     key |= (1 << (grid[nx][ny] - 'a'));
                  }
                  if (grid[nx][ny] >= 'A' && grid[nx][ny] <=
                  'F') {
                     if (((key >> (grid[nx][ny] - 'A')) & 1)
                     == 0)
                     continue;
                  }
                  vector<int> state({ key, nx, ny });
                  if (visited.count(state))
                  continue;
                  q.push(state);
                  visited.insert(state);
               }
            }
         }
         level++;
      }
      return -1;
   }
};
main(){
   Solution ob;
   vector<string> v = {"@.a.#","###.#","b.A.B"};
   cout << (ob.shortestPathAllKeys(v));
}

실행 결과

입력:

{"@.a.#","###.#","b.A.B"}

출력:

8

복잡도 분석

탐색해야 할 상태의 총 개수는 좌표 경우의 수 n × m에 키 비트마스크 경우의 수 2^k(k는 키 개수, 최대 6)를 곱한 값입니다. 따라서 시간 복잡도와 공간 복잡도 모두 O(n × m × 2^k)입니다. 키의 개수가 최대 6개로 제한되어 있어 충분히 실용적인 범위 안에서 동작합니다.

정리

이 문제의 핵심은 "위치 + 보유 키"를 하나의 확장된 상태로 보고 BFS를 수행하는 것입니다. 비트마스크를 활용하면 키 보유 여부를 정수 하나로 압축해 관리할 수 있어, 방문 체크와 자물쇠 통과 판정을 비트 연산 한 번으로 빠르게 처리할 수 있다는 점이 인상적입니다. 상태 공간을 확장하는 사고방식은 다양한 그래프 탐색 문제에 응용할 수 있으니 꼭 기억해 두시기 바랍니다.