[BOJ]백준 1194번: 달이 차오른다, 가자/Bitmask, BFS

www.acmicpc.net/problem/1194

1194번: 달이 차오른다, 가자.

비트마스킹의 정석같은 문제
BFS로 출구를 탐색해야 하지만 최대 6개의 문과 열쇠가 있기 때문에 열쇠의 소지 정보를 비트로 표현해서 탐색 정보로 활용해야 한다

#include <iostream> #include <string> #include <queue> #include <algorithm> using namespace std; typedef struct { int x, y; }point; int n, m, dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 },answer= -1; string arr[51]; queue<pair<point, int>> q; bool visit[64][51][51]; bool safe(int x, int y) { return x >= 0 && x < m && y >= 0 && y < n; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 0; i < n; i++) { cin >> arr[i]; for (int j = 0; j < m; j++) if (arr[i][j] == '0') { point s = { j,i }; q.push(make_pair(s, 0)); visit[0][i][j] = 1; } } int time = 0; while (!q.empty()) { int size = q.size(); while (size--) { auto x = q.front(); q.pop(); point cur = x.first; if (arr[cur.y][cur.x] == '1') { answer = time; printf("%d", time); return 0; } for (int i = 0; i < 4; i++) { int nx = cur.x + dx[i], ny = cur.y + dy[i]; if (!safe(nx, ny) || visit[x.second][ny][nx]||arr[ny][nx]=='#')continue; int key = x.second; if(arr[ny][nx]>='A'&&arr[ny][nx]<='F'&&((key >> (arr[ny][nx] - 'A') & 1) != 1)) continue; if(arr[ny][nx]>='a'&&arr[ny][nx]<='f') key |= 1 << (arr[ny][nx] - 'a'); visit[key][ny][nx] = true; point next = { nx,ny }; q.push(make_pair(next, key)); } } time++; } printf("-1"); return 0; }