# 문제 설명
가로 M, 세로 N, 높이 H인 상자에 담긴 토마토들의 상태가 주어진다.
(1: 익은 토마토, 0: 익지않은 토마토, -1: 토마토가 없는 칸)
하루가 지날 때마다 익은 토마토의 상/하/좌/우/위/아래에 있는 익지 않은 토마토들이 익게 되는데, 모든 토마토가 익을 때까지 최소 얼마나 시간이 걸릴까? 를 구하는 문제이다.
# 문제 풀이
가로 M, 세로 N, 높이 H인 상자이므로 3차원 배열에 입력을 받으면 된다.
이 때 각 변수에 해당하는 값이 입력되는 순서는 (M,N,H) 순이다.
다만 입력을 받을 때, 즉 삼중 포문으로 3차원 배열에 입력받을 때는 H, M, N 순으로 입력을 받아야 맞다. (이 부분에서 헷갈리기 시작하면 문제 푸는 데에 한참이나 소요되므로 입력에 관한 설명을 주의해야 한다.)
토마토가 익는 최소 일수를 바꾸어 말하면 익은 토마토로부터 익지 않은 토마토까지 도달하는 최단 거리를 말하는 것과 동일하다.
그러므로 BFS로 풀이하는 것이 용이하겠다는 판단이 들어 BFS로 풀었다.
구조체 point를 만들어서 익은 토마토들의 각 좌표(int h,n,m)와 그 토마토가 최초로 익을 때까지 걸린 최소 일수(int ripe_day)를 저장하도록 했다.
큐를 queue Q로 만들어서 처음에 3차원 배열에 토마토 상태들을 입력받을 때 익은 토마토(값 1)가 발견되면 ripe_day를 0으로 하고 좌표들을 저장하여 큐에 초기값으로 넣어주었다.
BFS를 돌려서 Q.front()를 꺼내어(top) top 좌표의 상/하/좌/우/위/아래에 익지않은 토마토가 발견되면 큐에 다시 넣어지지 않도록 익은 토마토로 만들어주고(box[hh][nn][mm] = 1), top.ripe_day보다 익는 데에 하루가 더 걸렸으므로 ripe_day에 top.ripe_day + 1을 넣어 큐에 다시 넣어주었다.
이때, top.ripe_day + 1가 result(모든 토마토가 익는 데에 걸리는 최소 일수)보다 크게 되면 result에 top.ripe_day + 1 값을 저장하였다. 모든 토마토가 익는 데에 걸리는 최소 일수가 가장 큰 값으로 갱신된 것이므로 이 작업은 꼭 해주어야 한다.
큐가 빈 상태가 되어 while문이 끝나게 되면, 익은 토마토들(원래부터 익어있었던 토마토 + 중간에 익은 토마토)을 모두 방문한 것이므로 상자에 익지 않은 채로 남아있는 토마토가 있는지 확인해야 한다.
확인해서, 익지 않은 채로 남아있으면 모든 토마토가 익을 수는 없었던 것(all_ripe == false)이므로 -1을 출력하고, 모든 토마토가 익었으면 result를 출력하고 종료한다.
// 7569. 토마토
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
int result;
int M, N, H;
int box[101][101][101];
int day_rec[101][101][101];
int dh[6] = { 0, 0, 0, 0, -1, 1 };
int dn[6] = { -1, 1, 0, 0, 0, 0 };
int dm[6] = { 0, 0, -1, 1, 0, 0 };
struct point {
int h;
int n;
int m;
int ripe_day;
};
queue<point> Q;
int main() {
cin >> M >> N >> H;
for (int i = 1; i <= H; i++) {
for (int j = 1; j <= N; j++) {
for (int k = 1; k <= M; k++) {
cin >> box[i][j][k];
if (box[i][j][k] == 1) Q.push({ i,j,k,0 });
}
}
}
while (!Q.empty()) {
point top = Q.front();
Q.pop();
for (int i = 0; i < 6; i++) {
int hh = top.h + dh[i];
int nn = top.n + dn[i];
int mm = top.m + dm[i];
if (hh < 1 || nn < 1 || mm < 1 || hh > H || nn > N || mm > M) continue;
if (box[hh][nn][mm] == 0) {
Q.push({ hh, nn, mm, top.ripe_day + 1 });
if (top.ripe_day + 1 > result) result = top.ripe_day + 1;
box[hh][nn][mm] = 1;
}
}
}
bool all_ripe = true;
for (int i = 1; i <= H; i++) {
for (int j = 1; j <= N; j++) {
for (int k = 1; k <= M; k++) {
if (box[i][j][k] == 0) {
all_ripe = false; break;
}
}
}
}
if (all_ripe) cout << result << endl;
else cout << -1 << endl;
}# 개선점 및 보완할 점
이 문제는 사실 알고리즘 자체는 간단했다. 그런데 처음에는 큐로 풀 생각을 하지 않고 3차원 배열을 계속해서 돌면서 익은 토마토가 발견될 때마다 상하좌우아래를 탐색하여 익게하는 방식으로 구현하다보니 시간초과가 났다. 알고리즘이 간단하다고 해서 무작정 구현했었기 때문에 일어난 뼈아픈 실책이었다. 이후에 정신차리고 BFS로 전환했을 때에도 BFS 내에서 3차원 배열을 계속해서 탐색하려고 해서 반복적으로 시간초과가 났다.
글 초기에 적은 것처럼, 토마토가 익는 최소 일수 = 최단 거리라는 개념을 간파했어야 했고, 문제를 이해했다고해서 바로 구현하는 습관보다는 지금 내가 생각한 알고리즘의 시간복잡도와 메모리사용량(공간)을 고려하는 습관을 들여야겠다고 느꼈던 문제였다.
