백준 7569 - 토마토

문제 : https://www.acmicpc.net/problem/7569

 

풀이과정

NxMxH 3차원 배열을 입력받아, 이미 익은 토마토를 저장 후 bfs 탐색을 진행하면 해결할 수 있다.

+ 이때 익지않은 토마토의 개수를 미리 세어주면 나중에 불필요한 탐색을 진행하지 않아도 된다.

 

풀이

1. 익은 토마토의 위치를 전부 저장한다.

동시에 익지 않은 토마토의 개수를 unripes 변수에 저장한다.

// 높이, 세로, 가로
deque < pair < int, pair < int , int > > > dq;

if(tomato[i][j][k] == 1) dq.push_back({i,{j,k}});
else if(tomato[i][j][k] == 0) unripes++;

 

2. 만약 익지 않은 토마토가 하나도 없다면, 바로 0을 출력하며

그렇지 않다면 solution을 진행하여 날짜를 구하면 된다.

if(unripes == 0) {
    printf("0\n");
}
else {
    solution();
    (unripes == 0) ? printf("%d\n",days-1) : printf("-1\n");
}

* 주의할 점은, 익은 토마토를 따로 저장하여 하나씩 bfs문을 돌리게 된다면 제대로 된 날짜를 구할 수 없다.

왜냐하면 처음 익어있는 토마토들이 동시에 주위 토마토를 익히지 못하기 때문이다.

 

 

2-1. bfs문을 살펴보면, 상,하,좌,우 에 있는 토마토를 익히고, 위,아래 에 있는 토마토를 동시에 익힌다.

만약 익는 토마토가 발생하면 unripes의 값을 하나씩 줄여나간다.

        // 상하좌우
        for(int i=0; i<4; i++) {
            int ny = sy + dy[i];
            int nx = sx + dx[i];
            if(ny >= N || ny < 0 || nx >= M || nx < 0) continue;
            if(tomato[sh][ny][nx] == 0) {
                tomato[sh][ny][nx] = tomato[sh][sy][sx] + 1;
                days = (days > tomato[sh][ny][nx]) ? days : tomato[sh][ny][nx];
                dq.push_back({sh,{ny,nx}});
                unripes--;
            }
        }
        // 위아래
        for(int i=0; i<2; i++) {
            int nh = sh + dh[i];
            if(nh >= H || nh < 0) continue;
            if(tomato[nh][sy][sx] == 0) {
                tomato[nh][sy][sx] = tomato[sh][sy][sx] + 1;
                days = (days > tomato[nh][sy][sx]) ? days : tomato[nh][sy][sx];
                dq.push_back({nh,{sy,sx}});
                unripes--;
            }
        }

 

 

코드

#include <iostream>
#include <stdio.h>
#include <deque>
#include <string.h>
using namespace std;
int tomato[100][100][100];
int N,M,H;
int days = 0, unripes = 0;
deque < pair < int, pair < int , int > > > dq;
int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,-1,1};
int dh[2] = {-1,1};

void solution() {

    while(!dq.empty()) {
        int sh = dq.front().first;
        int sy = dq.front().second.first;
        int sx = dq.front().second.second;
        dq.pop_front();

        // 상하좌우
        for(int i=0; i<4; i++) {
            int ny = sy + dy[i];
            int nx = sx + dx[i];
            if(ny >= N || ny < 0 || nx >= M || nx < 0) continue;
            if(tomato[sh][ny][nx] == 0) {
                tomato[sh][ny][nx] = tomato[sh][sy][sx] + 1;
                days = (days > tomato[sh][ny][nx]) ? days : tomato[sh][ny][nx];
                dq.push_back({sh,{ny,nx}});
                unripes--;
            }
        }
        // 위아래
        for(int i=0; i<2; i++) {
            int nh = sh + dh[i];
            if(nh >= H || nh < 0) continue;
            if(tomato[nh][sy][sx] == 0) {
                tomato[nh][sy][sx] = tomato[sh][sy][sx] + 1;
                days = (days > tomato[nh][sy][sx]) ? days : tomato[nh][sy][sx];
                dq.push_back({nh,{sy,sx}});
                unripes--;
            }
        }
    }
}

int main() {
    scanf("%d %d %d",&M,&N,&H);
    for(int i=0; i<H; i++) {
        for(int j=0; j<N; j++) {
            for(int k=0; k<M; k++) {
                scanf("%d",&tomato[i][j][k]);
                if(tomato[i][j][k] == 1) dq.push_back({i,{j,k}});
                else if(tomato[i][j][k] == 0) unripes++;
            }
        }
    }
    if(unripes == 0) {
        printf("0\n");
    }
    else {
        solution();
        (unripes == 0) ? printf("%d\n",days-1) : printf("-1\n");
    }
}