[BOJ] 9328 - 열쇠

https://www.acmicpc.net/problem/9328

BOJ - 열쇠

문제 유형: 구현, bfs, 그래프, 시뮬레이션

문제 난이도: Gold I

시간 제한: 1초

메모리 제한: 256MB

 

문제

상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다. 상근이는 상하좌우로만 이동할 수 있다.

상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.

각 테스트 케이스의 첫째 줄에는 지도의 높이와 너비 h와 w (2 ≤ h, w ≤ 100)가 주어진다. 다음 h개 줄에는 빌딩을 나타내는 w개의 문자가 주어지며, 각 문자는 다음 중 하나이다.

• '.'는 빈 공간을 나타낸다.
• '*'는 벽을 나타내며, 상근이는 벽을 통과할 수 없다.
• '$'는 상근이가 훔쳐야하는 문서이다.
• 알파벳 대문자는 문을 나타낸다.
• 알파벳 소문자는 열쇠를 나타내며, 그 문자의 대문자인 모든 문을 열 수 있다.

마지막 줄에는 상근이가 이미 가지고 있는 열쇠가 공백없이 주어진다. 만약, 열쇠를 하나도 가지고 있지 않는 경우에는 "0"이 주어진다.

상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있다. 각각의 문에 대해서, 그 문을 열 수 있는 열쇠의 개수는 0개, 1개, 또는 그 이상이고, 각각의 열쇠에 대해서, 그 열쇠로 열 수 있는 문의 개수도 0개, 1개, 또는 그 이상이다. 열쇠는 여러 번 사용할 수 있다.

 

출력

각 테스트 케이스 마다, 상근이가 훔칠 수 있는 문서의 최대 개수를 출력한다.

 

풀이

처음에 맵으로 들어가기 까다로울 수 있다.

그러나, 간편하게 하기 위해서는, 패딩을 적용하는 방법이 있다.

한 칸씩 더 둘러싸서 (0, 0)부터 시작해주면 된다. 그리고 패딩은 모두 '.'으로 가정하는 것이다.

처음에 입력받을 때에 대문자들의 위치를 별도로 저장해주자. 나중에 열쇠를 얻고 열러 가야하기 떄문이다.

 

bfs로 순회하는 중, 대문자를 만났는데 열쇠가 있다면 방문처리하고 큐에 넣고, 열쇠가 없다면 방문상태를 특수상태로 둔다. 나중에 열쇠를 찾으면 열러 오겠다는 의미이다.

만약 소문자를 만났다면, 열쇠를 얻는다. 그리고, 특수상태의 방문상태에 있는 대응되는 문들을 열어준다. 그러고 방문처리하고 큐에 넣는다.

만약 '.'이라면 그냥 큐에 넣고 방문처리한다.

만약 '$'이라면 카운트를 1 늘이고 큐에 넣고 방문처리한다.

 

최종적인 개수를 출력해주면 된다.

 

코드

C++

#include <bits/stdc++.h>
#define pii pair<int, int>

using namespace std;

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

void solve() {
  int h, w;
  cin >> h >> w;

  int ans = 0;
  vector<vector<char>> mat(h + 2, vector<char>(w + 2, '.'));
  vector<vector<short>> visited(h + 2, vector<short>(w + 2, false));
  vector<vector<pii>> doorMap(26);
  vector<bool> hasKey(26, false);
  queue<pii> q;
  for (int i = 0; i < h; ++i) {
    string temp;
    cin >> temp;
    for (int j = 0; j < w; ++j) {
      mat[i + 1][j + 1] = temp[j];
      if (mat[i + 1][j + 1] >= 'A' && mat[i + 1][j + 1] <= 'Z') {
        doorMap[mat[i + 1][j + 1] - 'A'].push_back({i + 1, j + 1});
      }
    }
  }

  string keys;
  cin >> keys;
  if (keys != "0") {
    for (char key : keys) {
      hasKey[key - 'a'] = true;
    }
  }

  q.push({0, 0});
  while (!q.empty()) {
    auto curr = q.front();
    int x = curr.first;
    int y = curr.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 + 2 || ny >= w + 2 ||
          visited[nx][ny] != 0)
        continue;

      if (mat[nx][ny] >= 'A' && mat[nx][ny] <= 'Z') {
        if (hasKey[mat[nx][ny] - 'A']) {
          q.push({nx, ny});
          visited[nx][ny] = 1;
        } else {
          visited[nx][ny] = 2;
        }
      } else if (mat[nx][ny] >= 'a' && mat[nx][ny] <= 'z') {
        q.push({nx, ny});
        visited[nx][ny] = 1;
        if (!hasKey[mat[nx][ny] - 'a']) {
          hasKey[mat[nx][ny] - 'a'] = true;
          for (const auto &elem : doorMap[mat[nx][ny] - 'a']) {
            if (visited[elem.first][elem.second] == 2) {
              visited[elem.first][elem.second] = 1;
              q.push({elem.first, elem.second});
            }
          }
        }
      } else if (mat[nx][ny] == '$') {
        ans++;
        q.push({nx, ny});
        visited[nx][ny] = 1;
      } else if (mat[nx][ny] == '.') {
        q.push({nx, ny});
        visited[nx][ny] = 1;
      }
    }
  }

  cout << ans << "\n";
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  int t;
  cin >> t;
  while (t--)
    solve();
  return 0;
}