[백준 1194] 달이 차오른다, 가자. (BFS, Bitmask) (C/C++) (★★★)

#include <stdio.h>
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
typedef struct node
{
    int x;
    int y;
    int key; // 가지고 있는 키의 합 
    int cnt;
}node;
 
char map[55][55];
int row, col;
int startX, startY;
int ans = -1;
 
queue<node> q;
int visited[55][55][64]; // 비트연산 사용 A(1), B(2), C(4), D(8), E(16), F(32) -> 최대합 2^6-1 이기때문에 64만큼의 배열 선언 
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
int safe(int x, int y)
{
    if(x >= 0 && x < row && y >= 0 && y < col)
    {
        return 1;
    }
    else
    {
        return 0;
    }
} 
 
void BFS()
{
    visited[startX][startY][0] = 1;
    q.push({startX, startY, 0, 0});
    
    while(!q.empty())
    {
        int x = q.front().x;
        int y = q.front().y;
        int key = q.front().key;
        int cnt = q.front().cnt;
        q.pop();
        
        if(map[x][y] == '1')
        {
            ans = cnt;
            return;
        }
        
        for(int i = 0; i < 4; i++)
        {
            int    xpos = x+dx[i];
            int ypos = y+dy[i];
            
            if(safe(xpos, ypos) == 1 && (map[xpos][ypos] == '.' || map[xpos][ypos] == '0' || map[xpos][ypos] == '1') && visited[xpos][ypos][key] == 0)
            {
                visited[xpos][ypos][key] = 1;
                q.push({xpos, ypos, key, cnt+1});    
            }
            // 열쇠를 찾음 
            else if(safe(xpos, ypos) == 1 && 'a' <= map[xpos][ypos] && map[xpos][ypos] <= 'f' && visited[xpos][ypos][key] == 0)
            {
                // 안 찾은 열쇠면 
                if((key & (1 << map[xpos][ypos] - 'a')) != (1 << map[xpos][ypos] - 'a'))
                {
                    int tempKey = key + (1 << (map[xpos][ypos] - 'a'));
                
                    visited[xpos][ypos][tempKey] = 1;
                    q.push({xpos, ypos, tempKey, cnt+1});    
                }
                // 찾은 열쇠면 
                else
                {
                    visited[xpos][ypos][key] = 1;
                    q.push({xpos, ypos, key, cnt+1});    
                }
            }
            // 문을 찾음 
            else if(safe(xpos, ypos) == 1 && 'A' <= map[xpos][ypos] && map[xpos][ypos] <= 'F' && visited[xpos][ypos][key] == 0)
            {
                // 문을 열 열쇠가 있는지 확인 
                if((key & (1 << map[xpos][ypos] - 'A')) == (1 << map[xpos][ypos] - 'A'))
                {    
                    visited[xpos][ypos][key] = 1;
                    q.push({xpos, ypos, key, cnt+1});
                }
            }
        }    
    }
}
 
int main(void)
{
//    freopen("B1194_input.txt", "r", stdin);
    
    cin >> row >> col;
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            cin >> map[i][j];
            
            if(map[i][j] == '0')
            {
                startX = i;
                startY = j;
            }
        }
    }
    
    BFS();
    
    cout << ans;
        
    return 0;
}