백준 1194번. 달이 차오른다, 가자(c++) / BFS+비트마스킹

백준 9328번. 열쇠 문제와 매우 유사하다.

다만, 차이점이라면 열쇠문제는 최소 거리를 구하는 것이 아닌 찾을 수 있는 문서의 개수이고

이 문제는 거리를 구해야했다.

 

따라서, 단순히 문을 저장해서 해결할 수 있는 것이 아니기 때문에 visited배열에 (x, y, 키의 저장상태) 를 저장해주었다.

그래서 같은 위치를 방문하더라도 키의 저장상태가 다르다면 그 위치에 접근할 수 있도록 했다.

 

// 달이 차오른다, 가자
#include <iostream>
#include <queue>
#include <tuple>
#include <string>
 
using namespace std;
 
string s;
int n, m;
char maze[51][51];
int startX, startY;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
 
// 애초에 '열쇠' 문제와 다르게, visited로 비트마스크 처리가 가능한 이유는
// 키의 범위가 'a'~'f'로 매우 작기 때문..!
 
bool check(char c, int key)
{
   if ((key & (1 << (c - 'A'))) != 0) {
      return true;
   }
 
   return false;
}
 
int move()
{
   queue<tuple<int, int, int, int>> q;
   int visited[51][51][100] = { 0, }; // (x, y, 획득한 키 상태)
   q.push(make_tuple(startX, startY, 0, 0));
 
   while (!q.empty()) {
      int x, y, cnt, key;
      tie(x, y, cnt, key) = q.front();
      q.pop();
      visited[x][y][key] = true;
 
      if (maze[x][y] == '1') {
         return cnt;
      }
 
      for (int i = 0; i < 4; i++) {
         int nx = x + dx[i];
         int ny = y + dy[i];
         if (0 <= nx && nx < n && 0 <= ny && ny < m) {
            if (maze[nx][ny] == '#') continue;
            if (maze[nx][ny] == '.' || maze[nx][ny] == '1') {
                if(!visited[nx][ny][key]){
                    visited[nx][ny][key] = true;
                    q.push(make_tuple(nx, ny, cnt + 1, key));
                }
            }
            else if ('a' <= maze[nx][ny] && maze[nx][ny] <= 'f') {
               int newKey = key | (1 << (maze[nx][ny] - 'a'));
               if(!visited[nx][ny][newKey]){
                   visited[nx][ny][newKey] = true;
                    q.push(make_tuple(nx, ny, cnt + 1, newKey));
               }
            }
            else if ('A' <= maze[nx][ny] && maze[nx][ny] <= 'F') {
               if (check(maze[nx][ny], key) && !visited[nx][ny][key]) {
                    visited[nx][ny][key] = true;
                    q.push(make_tuple(nx, ny, cnt + 1, key));
               }
            }
         }
      }
   }
 
   return -1;
}
 
int main()
{
   cin >> n >> m;
   for (int i = 0; i < n; i++) {
      cin >> s;
      for (int j = 0; j < m; j++) {
         maze[i][j] = s[j];
         if (maze[i][j] == '0') {
            maze[i][j] = '.';
            startX = i;
            startY = j;
         }
      }
   }
 
   cout << move() << "\n";
   return 0;
}