1194번

1194번 - 달이 차오른다, 가자

생각해보다가 모르겠어서 결국 다른 분들의 아이디어를 따왔다..

나는 BFS 라고 하면 자꾸 이차원배열로만 해결하려는 습관이 있었는데, 이 문제를 보면서 깨달음을 얻었다.

차원을 하나 늘려주므로서, 모든 고민거리가 한순가에 해결됐다.

이 문제는 일단, 같은 정점을 여러번 방문할 수 있어야 하는데, 그 조건을 어떻게 할 것인가가 문제였다.

나는 처음에는 BFS를 여러번 돌릴까 생각을 했다. 이차원으로만 하려고 하니, 도저히 풀리지가 않았다.

정점에 방문할 때 어떤 키를 가지고 있는가? 를 기준으로 차원을 늘려서 문제를 풀다보니, 같은 정점을 여러번 방문하는 것에도 문제가 없었다.

또한 열쇠가 6개이므로 열쇠를 가지고 있는지 없는지는 비트마스크를 통해서 해결할 수 있었다.

또 이동횟수는 BFS의 뎁스를 통해서 답을 구할 수 있었다.

####

어떤 정점을 방문할 때, 한차원을 늘려서 상태를 설정해주는 방식으로 문제를 풀 수 있다.

비트마스크는 복잡하게 생각하지말고,  0을1로, 1을0으로 바꾸는 방법이 중요한 것 같다.

<정답 코드>

#include<iostream>
#include<queue>
using namespace std;
 
typedef struct
{
    int x;
    int y;
    int key;
} P;
 
bool check[51][51][1 << 6];
char map[51][51];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int n, m, sx, sy;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    P start;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> map[i][j];
            if (map[i][j] == '0')
            {
                start.x = i;
                start.y = j;
                start.key = 0;
            }
        }
    }
 
    int ans = -1;
    queue<P> q;
    q.push(start);
    check[start.x][start.y][start.key] = true;
    bool chk = true;
    while (!q.empty() && chk )
    {
        ans++;
        int size = q.size();
        for (int i = 0; i < size; i++)
        {
            int x = q.front().x;
            int y = q.front().y;
            int key = q.front().key;
            q.pop();
 
            if (map[x][y] == '1')
            {
                chk = false;
                break;
            }
 
            for (int d = 0; d < 4; d++)
            {
                P np;
                int nx = x + dx[d];
                int ny = y + dy[d];
                int nk = key;
 
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && map[nx][ny] != '#')
                {
                    if (map[nx][ny] >= 'a' && map[nx][ny] <= 'z')
                    {
                        nk = (key | (1<<(map[nx][ny] - 'a')));
                    }
 
                    if (map[nx][ny] >= 'A' && map[nx][ny] <= 'Z')
                    {
                        if (!(nk & (1 << (map[nx][ny] - 'A'))))
                        {
                            continue;
                        }
                    }    
 
                    if (!check[nx][ny][nk])
                    {
                        np.x = nx;
                        np.y = ny;
                        np.key = nk;
    
                        check[nx][ny][nk] = true;
                        q.push(np);
                    }
            
                }
            }
 
        }
    }
 
    if (chk)
    {
        cout << "-1\n";
    }
    else
    {
        cout << ans << endl;
    }
    
 
 
    return 0;
}