[BOJ] 9328. 열쇠

* BFS로 완전 탐색을 한다. 

* 열쇠 상태를 계속 저장한다. (keystate)

* 상근이는 빌딩 밖을 자유럽게 돌아다닐 수 있기 때문에 맵의 바깥쪽은 전부 '.'으로 만들어준다. 

*(0,0)부터 탐색을 시작한다. 

- 문을 만나면 지금 가지고 있는 키로 열 수 있는지 확인한다. 열 수 있다면 빈공간('.')으로 만들어준다. 

- 문서를 만나면 훔칠 수 있는 문서의 개수인 (res)를 1만큼 증가시키고 빈공간('.')으로 만들어준다. 

- 열쇠를 만나면 keystate를 비트마스킹을 이용하여 값을 변경해주고 빈 공간으로 만들어준다. 

- 여기서 중요한 것은 열쇠를 만났을 때 지금 까지 방문했던 좌표 중에 이제는 열 수 있는 문이 있을 수도 있기 때문에 

visited 배열을 초기화한다. (초기화하는 방법 말고도 여러가지 효율적인 방법이 존재할 수 있다.)

- 이제 위의 세 가지 경우를 거치고 나면 원래 빈공간('.') 인 경우와 위의 세 가지 경우에서 빈공간이 된 좌표가 있을 것이다. 

빈 공간은 큐에 넣어줘서 계속 탐색할 수 있도록 한다. 

 

 

 

#include <iostream> #include <vector> #include <queue> #include <cstring> using namespace std; int h, w; char map[104][104]; int keystate = 0; bool visited[104][104]; int ans = 0; int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1}; typedef pair<int, int> pp; void bfs() { queue<pp> q; q.push(pp(0, 0)); visited[0][0] = true; while (!q.empty()) { 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 || nx > h + 1 || ny < 0 || ny > w + 1 || visited[nx][ny]) continue; if ('A' <= map[nx][ny] && map[nx][ny] <= 'Z') { //문이라면 if ((keystate & (1 << (map[nx][ny] - 'A'))) > 0) { map[nx][ny] = '.'; } } if ('a' <= map[nx][ny] && map[nx][ny] <= 'z') { //열쇠 획득 keystate |= (1<<(map[nx][ny] - 'a')); map[nx][ny] = '.'; memset(visited, 0, sizeof(visited)); } if (map[nx][ny] == '$') { //문서 ans++; map[nx][ny] = '.'; } if (map[nx][ny] == '.') { visited[nx][ny] = true; q.push(pp(nx, ny)); } } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while (t--) { memset(visited, 0, sizeof(visited)); ans = 0; keystate = 0; cin >> h >> w; //바깥쪽은 상근이가 돌아다닐 수 있는 구역이다. for (int i = 1; i <= h; i++) { for (int j = 1; j <= w; j++) { cin >> map[i][j]; } } string key; cin >> key; for (int i = 0; i < key.size(); i++) { keystate |= (1 << (key[i] - 'a')); } for (int i = 0; i <= h+1; i++) { for (int j = 0; j <= w+1; j++) { if (i == 0 || i == h+1 || j == 0 || j == w+1) map[i][j] = '.'; } } bfs(); cout << ans << '\n'; } return 0; }