[백준] 7569번 토마토

문제: 7569번: 토마토

basic-algo-lecture/workbook/0x09.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x09.md at master · encrypted-def/basic-algo-lecture

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>
#include <list>

using namespace std;


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

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

    int m, n, h; // m: 가로, n: 세로, h: 높이
    cin >> m >> n >> h;

    vector<vector<vector<int>>> boards(h); // 3차원 ㄷㄷ
    vector<vector<vector<int>>> visits(h);
    vector<vector<vector<int>>> dists(h); // 토마토 자라는데 걸리는 일수

    // first: h, second: 세로, third: 가로
    queue<tuple<int, int, int>> nexts; // 다음 위치
    for (int i = 0; i < h; i++) {
        boards[i] = vector<vector<int>>(n);
        visits[i] = vector<vector<int>>(n);
        dists[i] = vector<vector<int>>(n);

        for (int j = 0; j < n; j++) {
            boards[i][j] = vector<int>(m);
            visits[i][j] = vector<int>(m);
            dists[i][j] = vector<int>(m);

            for (int k = 0; k < m; k++) {
                cin >> boards[i][j][k]; // 입력 받기

                // 처음부터 다 자란 상태의 토마토
                if (boards[i][j][k] == 1) {
                    dists[i][j][k] = 0;
                    nexts.push(make_tuple(i, j, k));
                    visits[i][j][k] = 1; // 방문 표시
                }
            }
        }
    }

    while (!nexts.empty()) {
        tuple<int, int, int> cur = nexts.front();
        nexts.pop();
        int curZ = get<0>(cur);
        int curX = get<1>(cur);
        int curY = get<2>(cur);

        // 위, 아래
        for (int i = 0; i < 2; i++) {
            int nz = curZ + dz[i];
            if (nz < 0 || nz >= h) continue;
            if (visits[nz][curX][curY] == 1 || boards[nz][curX][curY] == -1) continue;

            dists[nz][curX][curY] = dists[curZ][curX][curY] + 1; // 일수 계산
            boards[nz][curX][curY] = 1; // 자랐당!
            nexts.push(make_tuple(nz, curX, curY));
            visits[nz][curX][curY] = 1; // 방문 표시
        }

        // 상, 하, 좌, 우
        for (int i = 0; i < 4; i++) {
            int nx = curX + dx[i];
            int ny = curY + dy[i];

            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (visits[curZ][nx][ny] == 1 || boards[curZ][nx][ny] == -1) continue;

            dists[curZ][nx][ny] = dists[curZ][curX][curY] + 1; // 일수 계산
            boards[curZ][nx][ny] = 1; // 자랐당!
            nexts.push(make_tuple(curZ, nx, ny));
            visits[curZ][nx][ny] = 1; // 방문 표시
        }
    }

    int max = -1;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < m; k++) {
                // 안 익은 토마토가 있다면 -1 출력
                if (boards[i][j][k] == 0) {
                    cout << -1;
                    return 0;
                }

                if (dists[i][j][k] > max)
                    max = dists[i][j][k];
            }
        }
    }
    cout << max; // 다 자라는데 걸리는 일수
   
    return 0;
}

 

7576 토마토 문제에서 차원이 하나 늘어났다. 원래는 상하좌우만 확인하면 됐는데 이제는 위아래도 확인해야 한다. 

 

그냥 3차원 요소 접근하는 방법이랑 튜플 사용법 잘 알고 있으면 쉽게 해결할 수 있는 문제라고 생각한다. 3차원이라고 해서 확인하는게 어려워지는 것도 아니고 그냥 상하좌우 확인하던 것처럼 좌표값 줘서 확인하면 된다.

 

 

 

참고자료:

BaaaaaaaarkingDog | [실전 알고리즘] 0x09강 - BFS

[실전 알고리즘] 0x09강 - BFS

[C++] tuple 사용법 & 예제

[C++] tuple 사용법 & 예제