[C++] BOJ 9328 - 열쇠

 

 

BOJ 9328 - 열쇠 (https://www.acmicpc.net/problem/9328)

 

01. 🔎 문제 탐색

T: 테스트케이스 개수 $(T \leq 100)$
h, w: 높이와 너비 $(2 \leq h,w \leq 100)$

• 각 칸의 상태
  {
      '.': 빈 공간,
      '*': 벽,
      '$': 문서,
      (대문자): 문,
      (소문자): 열쇠
  }
• 문(대문자)은 그 알파벳이 나타내는 열쇠(소문자)로 열 수 있음
• 열쇠는 여러 번 사용 가능

 

• 상근이는 빌딩 밖에서 시작해, 가장자리의 벽이 아닌 부분 어디로든 빌딩으로 들나들 수 있음
  • 만약, 문이 있을 경우 그 문의 열쇠가 필요
• OUTPUT
  • 상근이가 훔칠 수 있는 문서의 최대 개수를 출력

01-1. 가능한 시간 복잡도

• 빌딩에 들어갈 수 있는 가장자리 탐색 최대 4*100 - 4 = 약 396회, 시간 복잡도 $O(2h + 2w - 4)$
• 빌딩에 들어간 뒤, 빌딩 내부 탐색 최대 100^2 = 약 10,000회, 시간 복잡도 $O(h * w)$
• 만약, 열쇠를 주웠을 경우 문을 열어 새로운 영역을 탐색할 수도 있으므로 열쇠를 주웠을 경우, 재탐색
  최악의 경우, 1번의 탐색에서 1개 열쇠를 주울 때마다 새로운 탐색이 발생하여 27번 탐색이 이루어질 수 있음
  이는 27 * (가장자리 탐색) * (빌딩 내부 탐색) = 약 106,920,000 회로 1초내에 해결 가능

01-2. 알고리즘 선택 

• BFS를 이용한 시뮬레이션 문제
  (단, 열쇠를 주웠을 경우, 재탐색이 실행되어야 함)

02. 📝 코드 설계하기

1. 상근이가 가지고 있는 평면도와 열쇠 정보를 입력 
2. 빌딩 내부로 진입할 수 있는 가장자리 탐색 ['.', '$', (대문자), (소문자)]하여,
   진입할 수 있다면 방문 처리 후 queue에 추가
   
   1. 만약, 가장자리에 문이 있을 경우 그 문에 맞는 열쇠를 지니고 있는 지 확인
   2. 열쇠가 있다면 진입할 수 있으므로, 방문 처리 후 queue에 추가
3. 빌딩 내부로 진입하여 현재 위치에 열쇠나, 문서가 있을 경우 줍고 현재 위치를 빈 칸('.')으로 저장
   1. 열쇠를 주웠을 경우 열쇠를 주웠다는 상태를 저장 (got_new_key = true)
   2. 문서를 주웠을 경우 문서 개수 + 1
4. BFS를 통해 빌딩 내부를 탐색
   
   1. 열쇠를 주웠을 경우 열쇠를 주웠다는 상태를 저장 (got_new_key = true)
   2. 문서를 주웠을 경우 문서 개수 + 1
   3. 문이 있을 경우, 그 문에 맞는 열쇠를 지니고 있다면 진입
5. 만약, 열쇠를 새로 주웠다면 2번부터 다시 시작하고, 아니라면 누적된 문서 개수를 반환하여 출력

03. 🛠️ 시도별 수정

1회차

• 최초 진입한 바닥에 열쇠나 문서가 있을 경우, 이를 줍는 처리를 하지 않아서 수정함

2회차

---

04. 🗝️ 정답 코드

#include <bits/stdc++.h>
using namespace std;
template <typename T>
using matrix = vector<vector<T>>;

int h, w;
vector<string> board;
vector<bool> has_key;

bool got_new_key;

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

bool is_valid(int x, int y){
  return (x >= 0 && x < h && y >= 0 && y < w);
}

bool is_key(char mark){
  return ('a' <= mark && mark <= 'z');
}
bool is_door(char mark){
  return ('A' <= mark && mark <= 'Z');
}
bool open_door(char mark){ 
  return (is_door(mark) && has_key[tolower(mark) - 'a']); 
}

bool is_entrypoint(char mark){
  return (mark == '.' || mark == '$' || is_key(mark) || open_door(mark));
}

int search(){
  matrix<bool> visited(h, vector<bool>(w, false));
  queue<pair<int, int>> q;

  int doc_cnt = 0;

  for(int i = 0; i < h; i++){
    if(is_entrypoint(board[i][0]) && !visited[i][0]) {
      q.emplace(i, 0);
      visited[i][0] = true;
    }
    if(is_entrypoint(board[i][w-1]) && !visited[i][w-1]) {
      q.emplace(i, w-1);
      visited[i][w-1] = true;
    }
  }
  for(int j = 0; j < w; j++){
    if(is_entrypoint(board[0][j]) && !visited[0][j]) {
      q.emplace(0, j);
      visited[0][j] = true;
    }
    if(is_entrypoint(board[h-1][j]) && !visited[h-1][j]) {
      q.emplace(h-1, j);
      visited[h-1][j] = true;
    }
  }

  while(!q.empty()){
    auto& [x, y] = q.front(); q.pop();
    char &mark = board[x][y];

    if(is_key(mark)) {
      int key_idx = mark - 'a'; 
      if(!has_key[key_idx]){
        has_key[key_idx] = true;
        got_new_key = true;
      }
      mark = '.';
    }
    else if(mark == '$') {
      doc_cnt++;
      mark = '.';
    }

    for(int i = 0; i < 4; i++){
      int nx = x + dx[i], ny = y + dy[i];

      if(!is_valid(nx, ny) || board[nx][ny] == '*' || visited[nx][ny]) continue;
      else if(is_door(board[nx][ny]) && !open_door(board[nx][ny])) continue;

      q.emplace(nx, ny);
      visited[nx][ny] = true;
    }
  }

  return doc_cnt;
}

int solution(){
  int doc_cnt = 0;
  got_new_key = true;

  while(got_new_key){
    got_new_key = false;
    doc_cnt += search();
  }

  return doc_cnt;
}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  int T;
  cin >> T;
  while(T--){
    string keys;

    cin >> h >> w;
    board.assign(h, "");
    has_key.assign(27, false);
    
    for(int i = 0; i < h; i++) cin >> board[i];

    cin >> keys;
    if(keys != "0")
      for(auto& key : keys) has_key[key - 'a'] = true;

    cout << solution() << "\n";
  }

  return 0;
}