[BOJ] 9328. 열쇠

* BFS로 완전 탐색을 한다. 

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

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

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

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

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

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

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

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

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

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

 

 

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114

#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; }