[백준] 7576 토마토

eunbi·2022년 9월 19일
0

알고리즘 문제 풀이

목록 보기
17/18
post-thumbnail

🔍 7576 토마토

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.

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

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


🤔 풀이

1. 현재 창고에서 하루가 지나면 어떤 창고의 모습이 되는지 시뮬레이션 해본다.
	1-1. 창고의 격자를 하나씩 탐색하며 익은 토마토인지 확인한다. (N*M)
    1-2. 만약 익은 토마토라면 상하좌우에 익지 않은 토마토가 있는지 확인하고 해당 토마토를 익게 한다.
2. 아직 익지 않은 토마토가 몇 개인지 전체 탐색으로 카운트해보고 (N*M), 만약 익지 않은 토마토가 존재한다면 다시 시뮬레이션 한다.
  • 토마토가 모두 익지 않는 경우가 있을 수도 있으므로, 최대 시뮬레이션 수는 N * M으로 가정하고 풀었다. 따라서 최악의 경우 O(N2M2)=O(1012)O(N^2 * M^2) = O(10^{12}) 로 제한시간인 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;
}

0개의 댓글