[C++] 백준 7576 : 토마토

#include <iostream>
#include <utility> //pair
#include <queue>
using namespace std;

int map[101][101][101]; // 1 : 익은 토마토, 0 : 익지 않은 토마토, -1 : 토마토 없음
queue<pair<pair<int, int>, int> > q; // h, y, x

// 상하좌우위아래 탐색
int dx[6] = {1, -1, 0, 0, 0, 0};
int dy[6] = {0, 0, 1, -1, 0, 0};
int dh[6] = {0, 0, 0, 0, 1, -1};

bool allTomato = true; // 모든 토마토 익어있는 경우

int M, N, H; // 가로, 세로, 높이
int cnt = 0; // 토마토 모두 익을 때 까지 걸리는 시간

void BFS(){
  while(!q.empty()){
    int x = q.front().second; 
    int y = q.front().first.second;
    int h = q.front().first.first; // 노드의 좌표 구하기
    q.pop();

    for(int i = 0; i < 6; i++){
      int nx = x + dx[i];
      int ny = y + dy[i];
      int nh = h + dh[i];

      if(nx < 1 || ny < 1 || nh < 1 || nx > M || ny > N || nh > H){
        continue;
      }

      if(map[nh][ny][nx] == 0){ // 안익은 토마토가 있을 때
        map[nh][ny][nx] = map[h][y][x] + 1; // 날짜 더하기
        q.push({{nh, ny}, nx});
      }
    }
  }
}

int main(int argc, char* argv[]){
  scanf("%d %d %d", &M, &N, &H);

  for(int i=1; i<=H; i++){
    for(int j=1; j<=N; j++){
      for(int k=1; k<=M; k++){
        scanf("%d", &map[i][j][k]); // 입력받기
        if(map[i][j][k] == 1){ // 익은 토마토일 때
          q.push({{i, j}, k});
        } else if(map[i][j][k] == 0){
          allTomato = false;
        }
      }
    }
  }

  if(allTomato){ // 처음부터 모든 토마토 익어있는 경우
    printf("0");
    return 0;
  }

  BFS();

  // for(int i=1; i<=H; i++){
  //   for(int j=1; j<=N; j++){
  //     for(int k=1; k<=M; k++){
  //       printf("%d ", map[i][j][k]);
  //     }
  //     printf("\n");
  //   }
  // }

  for(int i=1; i<=H; i++){
    for(int j=1; j<=N; j++){
      for(int k=1; k<=M; k++){
        if(map[i][j][k] == 0){ // 모두 익지 않았을 때
          printf("-1");
          return 0;
        }
        if(cnt < map[i][j][k]){ // 최대 일 수 구하기
          cnt = map[i][j][k];
        }
      }
    }
  }

  printf("%d", cnt-1); // 토마토 익은 것 1부터 시작

  return 0;
}

7576 토마토의 업그레이드 버전 문제

• 상하좌우위아래 를 확인하기 위해서는 위로 갈 경우, 아래로 갈 경우, 좌로 갈 경우, 우로 갈 경우... 해서 6가지의 경우 수만 확인하면 된다. 이걸 조심하자. 처음에는 모든 경우의 수를 내가 배열에 넣어서 구하려고 했는데 굉장히 불필요한 일이었다.

• cnt를 세기 위해 바로 map으로 표시했기에 visit 여부는 표시할 필요가 없다. 때문에 7576 번에서 푼 것과 다르게 이번에는 visited를 아예 빼버렸다.

• pair에 값을 입력할 때, make_pair를 쓰는 것도 좋지만 {}를 쓰는 것이 훨씬 직관적이며 쉽다.