[C++] BOJ 23289 - 온풍기 안녕!

BOJ 23289 - 온풍기 안녕! (https://www.acmicpc.net/problem/23289)

 

나는 온풍기가 밉다.
 

01. 🔎 문제 탐색

• INPUT
  R: 세로 크기, C: 가로 크기, K: 원하는 온도
  + RxC 크기만큼 각 칸의 정보를 입력
  {0: 빈칸, 1: 오른쪽 온풍기, 2: 왼쪽 온풍기, 3: 위쪽 온풍기, 4: 아래쪽 온풍기, 5: 온도 조사할 칸}
  
  W: 벽의 개수
  + W개의 벽의 정보를 입력 (x, y, t)
  (t=0, (x, y)를 기준으로 위쪽에 벽이 있음 | t=1, (x, y)를 기준으로 오른쪽에 벽이 있음)
  
  
• 문제 흐름
  1. 모든 온풍기에서 동시에 바람이 1번 나옴
      1-1. 온풍기 바로 앞은 온도가 5도 상승
      1-2. 바로 앞을 시작으로, 앞으로 갈 수록 양 옆으로 1칸씩 범위가 넓어지며 온도가 5에서 1씩 감소한 값만큼 증가
  

  

  
      1-3. 바람의 진로 방향에 벽이 있을 경우, 벽 너머의 온도에는 영향이 없음
              - 오른쪽 바람에서 (x, y)를 기준으로 편의상 (x-1, y+1)를 왼쪽 칸, (x, y+1)를 앞 칸, (x+1, y+1)를 오른쪽 칸이라 함
              - 왼쪽 칸은 (x, y)와 (x-1, y) 사이 그리고 (x-1, y)와 (x-1, y+1) 사이에 벽이 있으면 안 됨
              - 앞 칸은 (x, y)와 (x, y+1) 사이에 벽이 있으면 안 됨
              - 오른쪽 칸은 (x, y)와 (x+1, y) 사이 그리고 (x+1,y)와 (x+1, y+1) 사이에 벽이 있으면 안 됨
  2. 온도 조절
      2-1. (x, y)의 온도를 동서남북 방향 인접한 칸의 온도와 각각 비교했을 때,
             (편의상, (x, y)의 온도를 기준 온도라고 함)
              - 기준 온도가 인접한 칸의 온도보다 높으면, ⌊(두 칸의 온도의 차이)/4⌋ 만큼을 기준 온도에서 빼준다.
              - 기준 온도가 인접한 칸의 온도보다 낮으면, ⌊(두 칸의 온도의 차이)/4⌋ 만큼을 기준 온도에서 더해준다.
      2-2. 1-3의 내용과 같이 인접한 칸이 벽으로 막혀있을 경우, 온도 조절은 발생하지 않음
  3. 가장 바깥쪽 칸의 온도가 1씩 감소 (0보다 낮아질 수 없음)
  4. 초콜릿을 하나 먹는다.
  5. 조사하는 모든 칸의 온도가 K이상 일경우, 테스트를 중단하고, 아니면 1부터 다시 시작
  
  
• OUTPUT
  (온풍기 가동 횟수) 먹은 초콜릿 개수 출력

 

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

• 가장 많은 연산이 발생하는 부분은 온풍기가 작동 될때
• 온풍기 작동 연산 횟수 (초콜릿 개수 * 방 크기 * 온풍기 최대 개수)  100 * 20 * 20 * 20 * 20  = 약 32e6회 연산으로,
  시간 복잡도 O((R*C)^2)으로 시간 제한 2초 내에 구현가능

01-2. 알고리즘 선택

• 단순 시뮬레이션으로 구현가능

02. 📝 코드 설계하기

1. 방 정보 입력 및 상태에 따라 저장
   1. 1-4 범위의 숫자가 입력되면, 온풍기로 현재 입력받는 좌표와 방향을 vector로 저장
   2. 5가 입력되면, 조사 영역으로 현재 좌표를 vector로 저장
2. 벽 정보 입력
   1. 좌표와 타입이 주어지면, 반대편에서도 확인할 수 있도록 3차원 배열을 이용해 벽 위치를 저장
      (Ex. (x, y, 1)이 입력되면, wall[x][y][오른쪽] = true, wall[x][y+1][왼쪽] = true)
3. 만약, 초콜릿의 개수가 100 이상이라면, 초콜릿 개수를 101로 하고 진행을 멈춤
4. 온풍기 가동
   1. 상태를 임시로 저장할 수 있는 임시 방 vector를 복사하여 만듦
   2. 첫번째 칸으로 진행할 수 있을 경우, 임시 vector에 온도를 5도 더하고 첫번째 칸을 Queue에 담음
   3. Queue에 담긴 첫번째 요소를 꺼내어 현재 위치로 지정
   4. 온풍기의 방향에 따라 진행하며, 현재 위치를 기준으로 왼쪽 대각, 앞, 오른쪽 대각 방향을 확인
   5. 각 방향이 주어진 방 내부, 처음 방문(온도 중복 상승 체크용), 진행 방향에 벽이 없을 경우 계속하고,
      아니면, 수행하지 않음
   6. 진행 방향의 칸의 위치에 맞는 온도를 임시 vector에 더하고 지금 칸을 Queue에 담음
      (저장해야 할 온도가 0도일 경우, Queue에 담지 않음)
   7. Queue의 원소가 없어질 때까지 4-3번부터 반복
5. 임시 vector를 방 온도 vector에 복사하여 정보를 업데이트
6. 온도 조절
   1. 각 칸을 순차적으로 탐색
   2. 현재 칸의 온도를 임시 vector에 저장
   3. 현재 칸을 기준으로 동서남북으로 인접한 칸과 온도를 비교
   4. 현재 칸의 온도가 높을 경우, ⌊(두 칸의 온도의 차이)/4⌋ 의 값을 임시 vector의 온도에서 빼줌
   5. 낮을 경우, ⌊(두 칸의 온도의 차이)/4⌋ 의 값을 임시 vector의 온도에서 더해줌
7. 임시 vector를 방 온도 vector에 복사하여 정보를 업데이트
8. 외곽의 온도를 1씩 감소 (0 일경우, 감소하지 않음)
9. 초콜릿 개수를 1개 추가
10. 조사 영역을 순차적으로 검사하여, 모든 칸의 온도가 K 이상이 아니라면, 3번으로 돌아가서 계속 진행
11. 초콜릿의 개수를 출력

 

03. 🛠️ 시도별 수정

1회차

• 온풍기 가동에서 방향에 따라 확산되는 함수를 하나로 리팩터링 가능할 것 같아서 다음에 시도해보는 걸로..

---

04. 🗝️ 정답 코드

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

int R, C, K;

vector<vector<int>> board(21, vector<int>(21, 0));
vector<vector<int>> new_board(21, vector<int>(21, 0));

const int UP = 0, DOWN = 1, LEFT = 2, RIGHT = 3;
int has_wall[21][21][4];

vector<pair<int, int>> examine;
vector<tuple<int, int, int>> warmer;

bool is_valid(pair<int, int> pos){
  auto& [x, y] = pos;
  return (x > 0 && x <= R && y > 0 && y <= C);
}

void update_board(){
  for(int i = 1; i <= R; i++){
    for(int j = 1; j <= C; j++){
      board[i][j] = new_board[i][j];
      new_board[i][j] = 0;
    }
  }
}

void move_up(pair<int, int> pos){
  vector<vector<bool>> is_visited(21, vector<bool>(21, false));
  queue<pair<int, int>> q;

  auto& [px, py] = pos;

  int nx = px - 1, ny = py;
  if(is_valid({nx, ny}) && !has_wall[nx][ny][DOWN]){
    is_visited[nx][ny] = true;
    new_board[nx][ny] += 5;
    q.push({nx, ny});
  }

  while(!q.empty()){
    auto& [x, y] = q.front(); q.pop();
    
    int nxt_temp = 5 - (px - x);
    if(nxt_temp > 0){
      // 왼쪽
      nx = x - 1, ny = y - 1;
      if(is_valid({nx, ny}) && !is_visited[nx][ny] 
      && !has_wall[nx][ny][DOWN] && !has_wall[x][y][LEFT]){
        is_visited[nx][ny] = true;
        new_board[nx][ny] += nxt_temp;
        q.push({nx, ny});
      }

      // 직진
      nx = x - 1, ny = y;
      if(is_valid({nx, ny}) && !is_visited[nx][ny] && !has_wall[nx][ny][DOWN]){
        is_visited[nx][ny] = true;
        new_board[nx][ny] += nxt_temp;
        q.push({nx, ny});
      }

      // 오른쪽
      nx = x - 1, ny = y + 1;
      if(is_valid({nx, ny}) && !is_visited[nx][ny] 
      && !has_wall[nx][ny][DOWN] && !has_wall[x][y][RIGHT]){
        is_visited[nx][ny] = true;
        new_board[nx][ny] += nxt_temp;
        q.push({nx, ny});
      }
    }
  }
}

void move_down(pair<int, int> pos){
  vector<vector<bool>> is_visited(21, vector<bool>(21, false));
  queue<pair<int, int>> q;

  auto& [px, py] = pos;

  int nx = px + 1, ny = py;
  if(is_valid({nx, ny}) && !has_wall[nx][ny][UP]){
    is_visited[nx][ny] = true;
    new_board[nx][ny] += 5;
    q.push({nx, ny});
  }

  while(!q.empty()){
    auto& [x, y] = q.front(); q.pop();
    
    int nxt_temp = 5 - (x - px);
    if(nxt_temp > 0){
      // 왼쪽
      nx = x + 1, ny = y - 1;
      if(is_valid({nx, ny}) && !is_visited[nx][ny] 
      && !has_wall[nx][ny][UP] && !has_wall[x][y][LEFT]){
        is_visited[nx][ny] = true;
        new_board[nx][ny] += nxt_temp;
        q.push({nx, ny});
      }

      // 직진
      nx = x + 1, ny = y;
      if(is_valid({nx, ny}) && !is_visited[nx][ny] && !has_wall[nx][ny][UP]){
        is_visited[nx][ny] = true;
        new_board[nx][ny] += nxt_temp;
        q.push({nx, ny});
      }

      // 오른쪽
      nx = x + 1, ny = y + 1;
      if(is_valid({nx, ny}) && !is_visited[nx][ny] 
      && !has_wall[nx][ny][UP] && !has_wall[x][y][RIGHT]){
        is_visited[nx][ny] = true;
        new_board[nx][ny] += nxt_temp;
        q.push({nx, ny});
      }
    }
  }
}

void move_left(pair<int, int> pos){
  vector<vector<bool>> is_visited(21, vector<bool>(21, false));
  queue<pair<int, int>> q;

  auto& [px, py] = pos;

  int nx = px, ny = py - 1;
  if(is_valid({nx, ny}) && !has_wall[nx][ny][RIGHT]){
    is_visited[nx][ny] = true;
    new_board[nx][ny] += 5;
    q.push({nx, ny});
  }

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

    int nxt_temp = 5 - (py - y);
    if(nxt_temp > 0){
      // 왼쪽
      nx = x - 1, ny = y - 1;
      if(is_valid({nx, ny}) && !is_visited[nx][ny] 
      && !has_wall[nx][ny][RIGHT] && !has_wall[x][y][UP]){
        is_visited[nx][ny] = true;
        new_board[nx][ny] += nxt_temp;
        q.push({nx, ny});
      }

      // 직진
      nx = x, ny = y - 1;
      if(is_valid({nx, ny}) && !is_visited[nx][ny] && !has_wall[nx][ny][RIGHT]){
        is_visited[nx][ny] = true;
        new_board[nx][ny] += nxt_temp;
        q.push({nx, ny});
      }

      // 오른쪽
      nx = x + 1, ny = y - 1;
      if(is_valid({nx, ny}) && !is_visited[nx][ny] 
      && !has_wall[nx][ny][RIGHT] && !has_wall[x][y][DOWN]){
        is_visited[nx][ny] = true;
        new_board[nx][ny] += nxt_temp;
        q.push({nx, ny});
      }
    }
  }
}

void move_right(pair<int, int> pos){
  vector<vector<bool>> is_visited(21, vector<bool>(21, false));
  queue<pair<int, int>> q;

  auto& [px, py] = pos;

  int nx = px, ny = py + 1;
  if(is_valid({nx, ny}) && !has_wall[nx][ny][LEFT]){
    is_visited[nx][ny] = true;
    new_board[nx][ny] += 5;
    q.push({nx, ny});
  }

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

    int nxt_temp = 5 - (y - py);
    if(nxt_temp > 0){
      // 왼쪽
      nx = x - 1, ny = y + 1;
      if(is_valid({nx, ny}) && !is_visited[nx][ny] 
      && !has_wall[nx][ny][LEFT] && !has_wall[x][y][UP]){
        is_visited[nx][ny] = true;
        new_board[nx][ny] += nxt_temp;
        q.push({nx, ny});
      }

      // 직진
      nx = x, ny = y + 1;
      if(is_valid({nx, ny}) && !is_visited[nx][ny] && !has_wall[nx][ny][LEFT]){
        is_visited[nx][ny] = true;
        new_board[nx][ny] += nxt_temp;
        q.push({nx, ny});
      }

      // 오른쪽
      nx = x + 1, ny = y + 1;
      if(is_valid({nx, ny}) && !is_visited[nx][ny] 
      && !has_wall[nx][ny][LEFT] && !has_wall[x][y][DOWN]){
        is_visited[nx][ny] = true;
        new_board[nx][ny] += nxt_temp;
        q.push({nx, ny});
      }
    }
  }
}

void mix_temp(pair<int, int> pos){
  auto& [x, y] = pos;

  int mid_temp = board[x][y];
  new_board[x][y] = mid_temp;
  
  int dx[4] = {-1, 1, 0, 0};
  int dy[4] = {0, 0, -1, 1};

  for(int i = 0; i < 4; i++){
    int nx = x + dx[i], ny = y + dy[i];
    if(!is_valid({nx, ny}) || has_wall[x][y][i]) continue;

    int near_temp = board[nx][ny];

    int diff = abs(mid_temp - near_temp) / 4;
    if(mid_temp > near_temp) new_board[x][y] -= diff;
    else if(mid_temp < near_temp) new_board[x][y] += diff;
  }
}

void control_temp(){
  board[1][1] > 0 ? board[1][1]-- : 0;
  board[R][C] > 0 ? board[R][C]-- : 0;
  board[1][C] > 0 ? board[1][C]-- : 0;
  board[R][1] > 0 ? board[R][1]-- : 0;

  for(int i = 2; i < R; i++) {
    board[i][1] > 0 ? board[i][1]-- : 0;
    board[i][C] > 0 ? board[i][C]-- : 0;
  }
  for(int i = 2; i < C; i++) {
    board[1][i] > 0 ? board[1][i]-- : 0;
    board[R][i] > 0 ? board[R][i]-- : 0;
  }
}

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

  cin >> R >> C >> K;

  for(int i = 1; i <= R; i++){
    for(int j = 1; j <= C; j++){
      int state;
      cin >> state;

      if(state == 5) examine.push_back({i, j});
      else if(0 < state && state < 5) warmer.push_back({i, j, state});
    }
  }

  int W;
  cin >> W;
  for(int i = 0, x, y, t; i < W; i++){
    cin >> x >> y >> t;

    // x - 1 방향 벽
    if(t == 0){
      has_wall[x][y][UP] = true;
      if((x - 1) > 0) has_wall[x - 1][y][DOWN] = true;
    } 
    // y + 1 방향 벽
    else if(t == 1){
      has_wall[x][y][RIGHT] = true;
      if((y + 1) <= C) has_wall[x][y + 1][LEFT] = true;
    }
  }

  int choco = 0;
  while(choco <= 100){
    if(choco >= 100){ choco++; break; }

    for(int i = 1; i <= R; i++){
      for(int j = 1; j <= C; j++) new_board[i][j] = board[i][j];
    }

    for(auto& [x, y, dir] : warmer){
      if(dir == 1) move_right({x, y});
      else if(dir == 2) move_left({x, y});
      else if(dir == 3) move_up({x, y});
      else if(dir == 4) move_down({x, y});
    }
    update_board();

    for(int i = 1; i <= R; i++){
      for(int j = 1; j <= C; j++) mix_temp({i, j});
    }
    update_board();

    control_temp();

    choco++;

    bool all_done = true;
    for(auto& [x, y] : examine){
      if(board[x][y] < K){
        all_done = false;
        break;
      }
    }

    if(all_done) break;
  }

  cout << choco << "\n";
  
  return 0;
}