이전에 열쇠 문제와 비슷한 여러 키의 상태를 가지고 방문을 확인하면서 풀어야 할 문제를 푼 경험이 있어 비트마스킹을 이용해 문제풀이를 진행하였는데 알파벳의 갯수가 26개로 check의 크기가 [100][100][2^26]만큼 커지는걸 생각하지 못해 정답을 맞추지 못했다. 그리고 만약 위 방법이 됐더라도 방문했던 곳을 같은 다른 열쇠를 가진 상태로 재방문하여야 하기 때문에 시간 초과가 날 것이다.

오답

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

struct SANGN {
	int x;
	int y;
	int keys;
	int paper;
};

int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };

int result = 0;

int t;
char map[100][100];
int n, m;
int keys;
bool check[100][100][2^26];

void init() {
	memset(map, ' ', sizeof(map));
	memset(check, false, sizeof(check));
	result = 0;
	keys = 0;
	return;
}

void input() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
		}
	}
	//키 저장
	string s;
	cin >> s;
	if (s != "0") {
		for (int i = 0; i < s.size(); i++) {
			keys |= (1 << s[i] - 'a');
		}
		return;
	}
}

void bfs(int x, int y, int keys, int _paper) {
	queue<SANGN> q;
	q.push({ x,y,keys,0 });
	int paper = _paper;
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int keys = q.front().keys;
		paper = q.front().paper;
		q.pop();

		//cout << x << " " << y << " " << paper << endl;

		if (map[x][y] == '$') {
			paper += 1;
		}
		
		for (int z = 0; z < 4; z++) {
			int nx = x + dx[z];
			int ny = y + dy[z];
			if (check[nx][ny][keys] == false && map[nx][ny] != '#') {
				//상근이가 밖으로 나감
				if (nx<0 || nx>=n || ny < 0 || ny >= m) {
					for (int i = 0; i < n; i++) {
						if (map[i][0] != '#') {
							if ('A' <= map[i][0] && map[i][0] <= 'Z') {
								if (!(keys & (1 << map[i][0] - 'A'))) continue;
							}
							check[i][0][keys] = true;
							bfs(i, 0, keys, 0);
						}
						if (map[i][m - 1] != '#') {
							if ('A' <= map[i][0] && map[i][0] <= 'Z') {
								if (!(keys & (1 << map[i][0] - 'A'))) continue;
							}
							check[i][m - 1][keys] = true;
							bfs(i, m - 1, keys, 0);
						}
					}

					//위 가로 아래 가로
					for (int j = 0; j < m; j++) {
						if (map[0][j] != '#') {
							if ('A' <= map[0][j] && map[0][j] <= 'Z') {
								if (!(keys & (1 << map[0][j] - 'A'))) continue;
							}
							check[0][j][keys] = true;
							bfs(0, j, keys, 0);
						}
						if (map[n - 1][j] != '#') {
							if ('A' <= map[n - 1][j] && map[n - 1][j] <= 'Z') {
								if (!(keys & (1 << map[n - 1][j] - 'A'))) continue;
							}
							check[n - 1][j][keys] = true;
							bfs(n - 1, j, keys, 0);
						}
					}
				}
				//밖으로 안나가고 내부에서 <돔>=
				else {
					//만약 다음칸에 갔는데 키가 없으면 continue
					if ('A' <= map[nx][ny] && map[nx][ny] <= 'Z') {
						if (!(keys & (1 << map[nx][ny] - 'A'))) continue;
					}
					if ('a' <= map[nx][ny] && map[nx][ny] <= 'z') {
						keys |= 1 << map[nx][ny] - 'a';
					}
					check[nx][ny][keys] = true;
					q.push({ nx,ny,keys,paper });
				}
			}
		}
	}

	result = max(result, paper);

}

void solve() {
	//왼쪽 세로 오른쪽 세로
	for (int i = 0; i < n; i++) {
		if (map[i][0] != '#') {
			if ('A' <= map[i][0] && map[i][0] <= 'Z') {
				if (!(keys & (1 << map[i][0] - 'A'))) continue;
			}
			check[i][0][keys] = true;
			bfs(i, 0, keys , 0);
		}
		if (map[i][m-1] != '#') {
			if ('A' <= map[i][0] && map[i][0] <= 'Z') {
				if (!(keys & (1 << map[i][0] - 'A'))) continue;
			}
			check[i][m - 1][keys] = true;
			bfs(i, m - 1, keys , 0);
		}
	}

	//위 가로 아래 가로
	for (int j = 0; j < m; j++) {
		if (map[0][j] != '#') {
			if ('A' <= map[0][j] && map[0][j] <= 'Z') {
				if (!(keys & (1 << map[0][j] - 'A'))) continue;
			}
			check[0][j][keys] = true;
			bfs(0, j, keys , 0);
		}
		if (map[n-1][j] != '#') {
			if ('A' <= map[n - 1][j] && map[n - 1][j] <= 'Z') {
				if (!(keys & (1 << map[n - 1][j] - 'A'))) continue;
			}
			check[n-1][j][keys] = true;
			bfs(n-1, j, keys, 0);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> t;
	for (int q = 0; q < t; q++) {
		init();
		input();
		solve();
		cout << result;
	}

	return 0;
}

정답 출처

#include<iostream>
#include<cstring>
#include<string>
#include<queue>
 
#define endl "\n"
#define MAX 111
using namespace std;
 
int H, W, Answer;
char MAP[MAX][MAX];
bool Visit[MAX][MAX];
bool Key[26];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
string First_Key;
 
void Initialize()
{
    memset(MAP, 0, sizeof(MAP));
    memset(Visit, false, sizeof(Visit));
    memset(Key, false, sizeof(Key));
    First_Key.clear();
    Answer = 0;
}
 
void Input()
{
    cin >> H >> W;
    for (int i = 1; i <= H; i++)
    {
        for (int j = 1; j <= W; j++)
        {
            cin >> MAP[i][j];
        }
    }
 
    cin >> First_Key;
    for (int i = 0; i < First_Key.length(); i++)
    {
        if (First_Key[i] == '0') continue;
        Key[First_Key[i] - 'a'] = true;
    }
}
 
void BFS(int a, int b)
{
    queue<pair<int, int>> Q;
    queue<pair<int, int>> Door[26];
    Q.push(make_pair(a, b));
    Visit[a][b] = true;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx <= H + 1 && ny <= W + 1)
            {
                if (MAP[nx][ny] == '*' || Visit[nx][ny] == true) continue;
                Visit[nx][ny] = true;
 
                if ('A' <= MAP[nx][ny] && MAP[nx][ny] <= 'Z')
                {
                    if (Key[MAP[nx][ny] - 'A'] == true)
                    {
                        Q.push(make_pair(nx, ny));
                    }
                    else
                    {
                        Door[MAP[nx][ny] - 'A'].push(make_pair(nx, ny));
                    }
                }
                else if ('a' <= MAP[nx][ny] && MAP[nx][ny] <= 'z')
                {
                    Q.push(make_pair(nx, ny));
                    if (Key[MAP[nx][ny] - 'a'] == false)
                    {
                        Key[MAP[nx][ny] - 'a'] = true;
 
                        while (Door[MAP[nx][ny] - 'a'].empty() == 0)
                        {
                            Q.push(Door[MAP[nx][ny] - 'a'].front());
                            Door[MAP[nx][ny] - 'a'].pop();
                        }
                    }
                }
                else
                {
                    Q.push(make_pair(nx, ny));
                    if (MAP[nx][ny] == '$') Answer++;
                }
            }    
        }
    }
}
 
void Solution()
{
    BFS(0, 0);
}
 
void Solve()
{
    int Tc;
    cin >> Tc;
 
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
        cout << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}