문제 링크

🔷 분류

너비 우선 탐색, 그래프 이론, 그래프 탐색, 격자 그래프, 최단 경로

✒️ 문제 설명

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

⬅️ 입력

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마토들의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 이러한 N개의 줄이 H번 반복하여 주어진다.

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

➡️ 출력

여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산해서 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

💻 코드 (C++)

#include <iostream>
#include <queue>
#include <tuple>
#include <algorithm>
using namespace std;

int dx[6] = {0, 0, 0, 0, 1, -1}; // x: 열 방향
int dy[6] = {0, 0, 1, -1, 0, 0}; // y: 행 방향
int dz[6] = {1, -1, 0, 0, 0, 0}; // z: 높이 방향

int bor[102][102][102]; // 3차원 토마토 상태
int dis[102][102][102]; // 일 수 저장 배열
int m, n, h; // 가로, 세로, 높이

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  cin >> m >> n >> h;
  
  for(int z = 1; z <= h; z++) {
    for(int y = 1; y <= n; y++) {
      for(int x = 1; x <= m; x++) {
        cin >> bor[z][y][x];
      }
    }
  }

  queue<tuple<int, int, int>> q;

  for(int z = 1; z <= h; z++) {
    for(int y = 1; y <= n; y++) {
      for(int x = 1; x <= m; x++) {
        if(bor[z][y][x] == 1) {
          q.push({z, y, x});
          dis[z][y][x] = 0;
        } else if(bor[z][y][x] == 0) {
          dis[z][y][x] = -1;
        } else {
          dis[z][y][x] = -2;
        }
      }
    }
  }

  while(!q.empty()) {
    auto cur = q.front(); q.pop();
    int z = get<0>(cur);
    int y = get<1>(cur);
    int x = get<2>(cur);

    for(int i = 0; i < 6; i++) {
      int nz = z + dz[i];
      int ny = y + dy[i];
      int nx = x + dx[i];

      if(nz < 1 || ny < 1 || nx < 1 || nz > h || ny > n || nx > m) continue;
      if(dis[nz][ny][nx] != -1) continue;

      dis[nz][ny][nx] = dis[z][y][x] + 1;
      q.push({nz, ny, nx});
    }
  }

  int ans = 0;
  for(int z = 1; z <= h; z++) {
    for(int y = 1; y <= n; y++) {
      for(int x = 1; x <= m; x++) {
        if(bor[z][y][x] == 0 && dis[z][y][x] == -1) {
          cout << -1;
          return 0;
        }
        if(dis[z][y][x] >= 0)
          ans = max(ans, dis[z][y][x]);
      }
    }
  }

  cout << ans;
  return 0;
}

글 이동

Comments

참고