[백준] 9328 - 열쇠

이 문제는 bfs + 비트마스킹을 이용한 문제

다만, 열쇠를 찾았을때, 지나온 곳에 그 문이 있을때 어떻게 처리해줘야 할지가 가장 중요합니다

제가 사용한 방법은, 열쇠가 없는 문을 만났을 때 다른 구조체 배열에 위치와 문의 알파벳을 저장

열쇠를 찾는다면, 찾은 열쇠로 열 수 있는 문(열쇠가 없는 문을 저장해 구조체배열)을 찾아서 다시 큐에 담아줍니다.

#include <iostream>
#include <memory.h>
#define MX 110
using namespace std;
 
struct kkk {
    int t, x, y;
}q[MX*MX], sub[MX*MX];
 
char map[MX][MX], arr[MX];
int check[MX][MX];
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
int h, w, st, ed, ix, iy, nx, ny, subcnt, dab;
long long int key;
 
void bfs()
{
    st = ed = -1; subcnt = -1;
    q[++st].x = 0; q[st].y = 0; check[0][0] = 1;
    while (st != ed)
    {
        ix = q[++ed].x; iy = q[ed].y;
        for (int i = 0; i < 4; i++)
        {
            nx = ix + dx[i]; ny = iy + dy[i];
            if (nx < 0 || ny < 0 || nx >= w + 2 || ny >= h + 2) continue;
            if (map[ny][nx] == '*' || check[ny][nx]) continue;
            if (map[ny][nx] == '$') { dab++; q[++st].x = nx; q[st].y = ny; check[ny][nx] = 1; map[ny][nx] = '.'; }
            else if ('A' <= map[ny][nx] && map[ny][nx] <= 'Z')
            {
                if (key & (1 << (map[ny][nx] - 'A' + 1))) {    q[++st].x = nx; q[st].y = ny; check[ny][nx] = 1; map[ny][nx] = '.'; }
                else { sub[++subcnt].x = nx; sub[subcnt].y = ny; }
            }
            else if ('a' <= map[ny][nx] && map[ny][nx] <= 'z')
            {
                key |= (1 << (map[ny][nx] - 'a' + 1));
                q[++st].x = nx; q[st].y = ny; check[ny][nx] = 1; map[ny][nx] = '.';
                for (int k = 0; k <= subcnt; k++)
                {
                    if (key & 1 << (map[sub[k].y][sub[k].x] - 'A' + 1)) { q[++st].x = sub[k].x; q[st].y = sub[k].y; check[sub[k].y][sub[k].x] = 1; map[ny][nx] = '.'; }
                }
            }
            else { q[++st].x = nx; q[st].y = ny; check[ny][nx] = 1; }
        }
    }
}
 
int main(void)
{
    int T;
    cin >> T;
    while (T--)
    {
        memset(check, 0, sizeof(check));
        memset(map, '.', sizeof(map));
        memset(arr, 0, sizeof(arr));
        memset(q, 0, sizeof(q));
        memset(sub, 0, sizeof(sub));
        key = dab = 0;
        cin >> h >> w;
        for (int i = 1; i <= h; i++)
            for (int j = 1; j <= w; j++)
            {
                char c;
                cin >> c;
                map[i][j] = c;
            }
        cin >> arr;
        int k = 0;
        while (1)
        {
            if (arr[0] == '0') break;
            if (arr[k] == 0) break;
            key |= 1 << (arr[k] - 'a' + 1);
            k++;
        }
        bfs();
        cout << dab << endl;
    }
    return 0;
}