🔍 7576 토마토
철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.
창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.
토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.
🤔 풀이
- (시간초과) 최근 COS Pro 1급 Java 모의고사 - 꽃 피우기를 학습했기 때문에 이 또한 단순히 꽃 피우기 문제와 같은 방법으로 풀었다. (꽃피우기 케이스가 더 쉬웠다!)
1. 현재 창고에서 하루가 지나면 어떤 창고의 모습이 되는지 시뮬레이션 해본다.
1-1. 창고의 격자를 하나씩 탐색하며 익은 토마토인지 확인한다. (N*M)
1-2. 만약 익은 토마토라면 상하좌우에 익지 않은 토마토가 있는지 확인하고 해당 토마토를 익게 한다.
2. 아직 익지 않은 토마토가 몇 개인지 전체 탐색으로 카운트해보고 (N*M), 만약 익지 않은 토마토가 존재한다면 다시 시뮬레이션 한다.-
토마토가 모두 익지 않는 경우가 있을 수도 있으므로, 최대 시뮬레이션 수는 N * M으로 가정하고 풀었다. 따라서 최악의 경우 로 제한시간인 1초를 넘어버린다.
-
(고치기) 이 문제를 해결하기 위해서 창고를 모두 탐색하는 방법을 고쳐야한다.
-
예시를 들어 만약 2*2 의 창고가 있고, 모두 토마토로 채워져있다고 가정해보자. 이때 왼쪽 위의 한 토마토만 익은 토마토이다. 시간이 지나 왼쪽 위의 토마토 오른쪽, 아래에 있는 토마토가 익게 된다. 또 시간이 지나면 그 전날 새로 익은 토마토의 상하좌우에 있는 토마토가 익게 된다. 생각해보면, 익은 토마토가 한 번 상하좌우 토마토를 익게 만들면 다음부터는 해당 위치의 토마토 작용에 대해 신경을 쓸 필요가 없어진다는 뜻이다.
-
그렇기 때문에 새로 익은 토마토의 위치를 저장하는 배열(큐, 스택...)을 만들어 탐색 횟수를 크게 줄일 수 있다. 이렇게 되면 벽에 막혀 결국 익지 않은 토마토까지 처리할 수 있게 된다. (벽에 막혀 토마토가 익힘 작용을 못 하게되므로)
-
위의 경우일 때 이전 방법은 1000*1000*1000*1000(창고 크기에 의해) 번의 반복이 일어나지만, 개선된 방법은 단 한 번의 시뮬레이션밖에 일어나지 않는다! (이때는 창고 크기가 아닌 익힘 현상의 단계, 즉 새롭게 익은 토마토가 몇 번 생기는지 = 며칠이나 현상이 지속되는지에 따라 좌우된다.)
📝 코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define RIPE 1
#define NRIPE 0
int N, M, ans = 0;
int board[1000][1000];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
queue<pair<int, int> > ripe;
int not_ripe_cnt;
void simulation() {
queue<pair<int, int> > new_ripe;
while (!ripe.empty()) {
int x = ripe.front().first;
int y = ripe.front().second;
ripe.pop();
for (int i = 0; i < 4; ++i) {
int nx = x+dx[i];
int ny = y+dy[i];
if (nx >= 0 && nx < N && ny >= 0 && ny < M && board[nx][ny] == NRIPE) {
board[nx][ny] = RIPE;
--not_ripe_cnt;
new_ripe.push(make_pair(nx, ny));
}
}
}
ripe = new_ripe;
if (!new_ripe.empty()) ++ans;
return ;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> M >> N;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
cin >> board[i][j];
if (board[i][j] == RIPE) ripe.push(make_pair(i, j));
if (board[i][j] == NRIPE) ++not_ripe_cnt;
}
}
while (!ripe.empty()) simulation();
if (not_ripe_cnt > 0) cout << -1;
else cout << ans;
return 0;
}