백준 7569 - 토마토 (c++)

백준 7569 - 토마토

문제 링크

생각 및 접근

• 2차원 토마토 문제는 해본 적이 있다. 3차원 토마토 문제를 처음 겪어보았다.

  • 2차원 토마토 문제 링크

• 우선, 토마토의 좌표를 나타내는 struct tomato를 선언했다.

    struct tomato {
        int x;
        int y;
        int z;
        tomato(int a, int b, int c) {
            x = a;  y = b;  z = c;
        }
    };

• 여섯 방향을 나타내는 dx[], dy[], dz[]를 선언했다.

    int dx[] = { 0, 1, 0, 0, -1, 0 };
    int dy[] = { 0, 0, 1, 0, 0, -1 };
    int dz[] = { 1, 0, 0, -1, 0, 0 };

• 토마토 정보를 m[101][101][101]에 받는다.

    // 익은 토마토일 경우, 익은 토마토를 기준으로 6 방향으로 나눠 안익은 토마토를 익혀가기 위해서 q에 추가한다.
    if (m[i][j][k] == 1)        q.push(make_pair(tomato(i, j, k), 0));
    // 비어있는 경우, emptyCnt++
    else if (m[i][j][k] == -1)  emptyCnt++;
    // 익지 않은 경우, rareCnt++
    else if (m[i][j][k] == 0)   rareCnt++;

• 토마토 상자 내에 있는 모든 토마토가 익어있는 경우를 처리한다.

    if (q.size() + emptyCnt == _x * _y * _z) {
        cout << 0;
        exit(0);
    }

• BFS를 실시한다.

    while (!q.empty()) {
        int x = q.front().first.x;
        int y = q.front().first.y;
        int z = q.front().first.z;
        int day = q.front().second;
        q.pop();
  
        // day에서 제일 큰 값이 전체 토마토가 다 익는 날짜가 된다.
        answer = max(answer, day);
  
        for (int i = 0; i < 6; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            int zz = z + dz[i];
  
            if (isRare(xx, yy, zz)) {
                // 이제는 익었으므로 하나 줄여준다.
                rareCnt--;
                // 익었으므로 1로 표기
                m[xx][yy][zz] = 1;
                // 익은 토마토를 기준으로 BFS
                q.push(make_pair(tomato(xx, yy, zz), day + 1));
            }
        }
    }

코드

#include <bits/stdc++.h>
using namespace std;

struct tomato {
    int x;
    int y;
    int z;
    tomato(int a, int b, int c) {
        x = a;  y = b;  z = c;
    }
};

int dx[] = { 0, 1, 0, 0, -1, 0 };
int dy[] = { 0, 0, 1, 0, 0, -1 };
int dz[] = { 1, 0, 0, -1, 0, 0 };

int m[101][101][101], _x, _y, _z, emptyCnt, rareCnt, answer = -2147000000;
queue< pair<tomato, int> > q;

bool isRare(int xx, int yy, int zz) {
    return xx >= 1 && xx <= _y && yy >= 1 && yy <= _x && zz >= 1 && zz <= _z && m[xx][yy][zz] == 0;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);

    cin >> _x >> _y >> _z;

    for (int k = 1; k <= _z; k++) {
        for (int i = 1; i <= _y; i++) {
            for (int j = 1; j <= _x; j++) {
                cin >> m[i][j][k];
                if (m[i][j][k] == 1)        q.push(make_pair(tomato(i, j, k), 0));
                else if (m[i][j][k] == -1)  emptyCnt++;
                else if (m[i][j][k] == 0)   rareCnt++;
            }
        }
    }

    if (q.size() + emptyCnt == _x * _y * _z) {
        cout << 0;
        exit(0);
    }

    while (!q.empty()) {
        int x = q.front().first.x;
        int y = q.front().first.y;
        int z = q.front().first.z;
        int day = q.front().second;
        q.pop();

        answer = max(answer, day);

        for (int i = 0; i < 6; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            int zz = z + dz[i];

            if (isRare(xx, yy, zz)) {
                rareCnt--;
                m[xx][yy][zz] = 1;
                q.push(make_pair(tomato(xx, yy, zz), day + 1));
            }
        }
    }

    if (rareCnt == 0)   cout << answer;
    else                cout << -1;
}

채점 결과