[백준 4991] 로봇 청소기 (BFS, Bitmask) (C/C++) (★★★)

#include <stdio.h>
#include <iostream>
#include <queue>
#include <string>
#include <string.h>
using namespace std;
 
typedef struct dNode
{
    int x;
    int y;
    int dirtyNum;
}dNode;
 
typedef struct qNode
{
    int x;
    int y;
    int clearDirty;
    int dist;
}qNode;
 
char Map[25][25];
int visited[25][25][1 << 11];
int row, col;
vector<dNode> dirty;
int dirtyCnt;
int clear;
int ans = -1;
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
int safe(int x, int y)
{
    if(x >= 0 && y >= 0 && x < row && y < col)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void BFS()
{
    queue<qNode> q;
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(Map[i][j] == 'o')
            {
                q.push({i, j, 0, 0});
                visited[i][j][0] = 1;
                break;
            }
        }
    }
    
    while(!q.empty())
    {
        int x = q.front().x;
        int y = q.front().y;
        int clearDirty = q.front().clearDirty;
        int dist = q.front().dist;
        q.pop();
        
        if(clear == clearDirty)
        {
            ans = dist;
            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] != 'x' && visited[xpos][ypos][clearDirty] == 0)
            {
                visited[xpos][ypos][clearDirty] = 1;
                q.push({xpos, ypos, clearDirty, dist+1});
            } 
            // 더러운 곳인 경우 
            else if(safe(xpos, ypos) == 1 && Map[xpos][ypos] == '*' && visited[xpos][ypos][clearDirty] == 0)
            {
                int findNum;
                
                for(int j = 0; j < dirty.size(); j++)
                {
                    if(dirty[j].x == xpos && dirty[j].y == ypos)
                    {
                        findNum = dirty[j].dirtyNum;
                        break;        
                    }
                }
                                
                // 깨끗하게 만들지 않은 칸이면
                if((clearDirty & (1 << findNum-1)) == 0)
                {
                    int tempClearDirty = clearDirty;
                    tempClearDirty += (1 << findNum-1);
                    
                    visited[xpos][ypos][tempClearDirty] = 1;
                    q.push({xpos, ypos, tempClearDirty, dist+1});
                }
                // 깨끗하게 만든 칸이면
                else
                {
                    visited[xpos][ypos][clearDirty] = 1;
                    q.push({xpos, ypos, clearDirty, dist+1});
                }     
            }
        }
    }
}
 
int main(void)
{
//    freopen("B4991_input.txt", "r", stdin);
    
    while(1)
    {
        memset(visited, 0, sizeof(visited));
        dirty.clear();
        dirtyCnt = 0;
        ans = -1;
        
        cin >> col >> row;
    
        if(row == 0 && col == 0)
        {
            return 0;
        }
        
        for(int i = 0; i < row; i++)
        {
            string temp;
            cin >> temp;
            
            for(int j = 0; j < temp.size(); j++)
            {
                Map[i][j] = temp[j];
                
                // 비트 연산을 위해 더러운 곳에 번호 부여 
                if(Map[i][j] == '*')
                {
                    dirty.push_back({i, j, ++dirtyCnt});
                }
            }
        }
        
        // 더러운 곳을 모두 채웠을 때의 비트 값 
        clear = (1 << dirtyCnt) - 1;
        
        BFS();
        
        cout << ans << endl;
    }
    
    return 0;
}