[C++] BOJ 2638 - 치즈

BOJ 2638 - 치즈 (https://www.acmicpc.net/problem/2638)

 

01. 🔎 문제 탐색

NxM 크기 공간
치즈의 2변 이상이 외부 공기와 접촉하면, 그 치즈는 1시간 후 녹게 됨
(단, 치즈 내부 공간은 접촉하지 않은 것으로 판단)
맨 가장자리에는 치즈가 놓이지 않음

INPUT
N, M 입력
NxM 크기만큼 상태 입력 (0: 공기, 1: 치즈)

OUTPUT
치즈가 모두 녹아 없어지게 되는 시간 출력

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

• N, M <= 100
  외부 공기와 맞닿은 공간 탐색 O(NM)
  치즈에 대해 탐색 O(NM)
• 치즈 탐색 1시간 당, 외부 공기 탐색 1회 진행하게 되므로, O(2NM)으로 볼 수 있다. 2e4로 1초내 충분히 수행가능

01-2. 알고리즘 선택

• BFS를 이용하여 외부 공기와 치즈에 대해 탐색을 요구하는 시뮬레이션 문제

 

02. 📝 코드 설계하기

1. N, M 그리고 NxM 크기 공간에 대한 상태(치즈와 공기) 입력
2. 치즈가 입력되면, 저장되는 위치 (x, y)를 queue에 추가
3. (0, 0) 위치부터 BFS를 수행하여 공기인 부분을 is_air(vector)에 저장
   (가장자리에는 치즈를 놓을 수 없기 때문에, 꼭짓점인 (0, 0)부터 탐색)
4. queue에 저장된 치즈를 순차적으로 꺼내어 4면을 탐색
   1. is_air를 조사하여 2면 이상이 참일 경우, 임시 공간 vector에 현재 치즈가 녹은 상태를 저장
   2. 아닐 경우, 다음 시간에 다시 조사하기 위하여 현재 위치(x, y)를 임시 queue에 추가
5. queue의 요소를 모두 꺼내어 탐색했을 경우, 시간을 1시간 증가시키고 상태 동기화
   
   1. queue에 다음에 조사할 치즈를 담고 있는 임시 queue의 데이터를 복사하고, 임시 queue를 초기화
   2. 임시 공간 vector를 현재 공간(공기와 치즈가 저장된 2차원 vector)에 복사
6. queue에 더 이상 조사할 치즈가 남아있지 않을 경우 소요된 시간을 반환하고, 아니면 3번부터 다시 수행

03. 🛠️ 시도별 수정

1회차

• 각 치즈에 대해서 동 시간에 조사된다는 것을 코드에 반영하지 못 했음
  • 임시 vector를 통해, 지금까지의 치즈 상태를 저장하고, queue에 담긴 모든 치즈를 조사가 끝나고 임시 vector를 원래 vector에 덮어씌우는 것으로 상태를 동기화, (다음에 조사할 치즈도 같은 방법으로 동기화)

2회차

---

04. 🗝️ 정답 코드

#include <bits/stdc++.h>
using namespace std;

int N, M;
vector<vector<int>> board;
vector<vector<bool>> is_air;
queue<pair<int, int>> cheese;
queue<pair<int, int>> next_cheese;

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 < N && y >= 0 && y < M);}

void mark_air(){
  vector<vector<bool>> visited(N, vector<bool>(M, false));
  queue<pair<int, int>> q;
  is_air.assign(N, vector<bool>(M, false));

  q.emplace(0, 0);
  visited[0][0] = true;

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

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

      if(!is_valid(nx, ny) || board[nx][ny] == 1 || visited[nx][ny]) continue;

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

int solution(){
  vector<vector<int>> tmp_board(N, vector<int>(M));
  tmp_board = board;

  int hours = 0;

  mark_air();
  while(!cheese.empty()){
    auto& [x, y] = cheese.front(); cheese.pop();

    int cnt_air = 0;
    for(int i = 0; i < 4; i++){
      int nx = x + dx[i], ny = y + dy[i];
      if(!is_valid(nx, ny)) continue;
      if(board[nx][ny] == 0 && is_air[nx][ny]) cnt_air++;
    }
    if(cnt_air >= 2) tmp_board[x][y] = 0;
    else next_cheese.emplace(x, y);

    if(cheese.empty()){
      hours++;
      if(!next_cheese.empty()){
        cheese = next_cheese;
        next_cheese = queue<pair<int, int>>();
      }
      board = tmp_board;
      mark_air();
    }
  }

  return hours;
}

int main(){
  ios::sync_with_stdio(0); cin.tie(0);

  cin >> N >> M;
  board.resize(N, vector<int>(M));

  for(int i = 0; i < N; i++)
    for(int j = 0; j < M; j++){
      cin >> board[i][j];
      if(board[i][j] == 1) cheese.emplace(i, j);
    }

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

  return 0;
}