백준 7569번 [토마토](C++) -yes6686- 티스토리

백준 문제 풀이: 7569 [토마토]

---

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

문제 설명:

상자에 보관된 토마토가 모두 익을 때까지 걸리는 최소 날짜를 계산하세요. 상자는 3차원 구조로 구성되며, 익은 토마토는 상하좌우, 앞뒤로 하루에 한 칸씩 영향을 미칩니다.

입력 조건:

• 첫 번째 줄에 상자의 가로 칸 수 M, 세로 칸 수 N, 상자의 수 H가 주어집니다. (2 ≤ M, N ≤ 100, 1 ≤ H ≤ 100)
• 다음 H × N개의 줄에 상자의 상태가 주어집니다. (1은 익은 토마토, 0은 익지 않은 토마토, -1은 빈 칸)

출력 조건:

• 모든 토마토가 익을 때까지 걸리는 최소 날짜를 출력합니다.
• 모든 토마토를 익게 만들 수 없다면 -1을 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int arr[101][101][101];
int visited[101][101][101];
int dis[101][101][101];
int dx[6] = {1, -1, 0, 0, 0, 0};
int dy[6] = {0, 0, 1, -1, 0, 0};
int dz[6] = {0, 0, 0, 0, 1, -1};
int m, n, h;

queue<tuple<int, int, int>> q;

void bfs() {
    while (!q.empty()) {
        int z = get<0>(q.front());
        int x = get<1>(q.front());
        int y = get<2>(q.front());
        q.pop();

        for (int i = 0; i < 6; i++) {
            int nz = z + dz[i];
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nz >= 0 && nz < h && nx >= 0 && nx < n && ny >= 0 && ny < m) {
                if (arr[nz][nx][ny] == 0 && !visited[nz][nx][ny]) {
                    visited[nz][nx][ny] = 1;
                    arr[nz][nx][ny] = 1;
                    dis[nz][nx][ny] = dis[z][x][y] + 1;
                    q.push({nz, nx, ny});
                }
            }
        }
    }
}

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

    cin >> m >> n >> h;
    bool allRipe = true;
    int maxDays = 0;

    for (int z = 0; z < h; z++) {
        for (int x = 0; x < n; x++) {
            for (int y = 0; y < m; y++) {
                cin >> arr[z][x][y];
                if (arr[z][x][y] == 1) {
                    q.push({z, x, y}); // 익은 토마토의 위치 추가
                    visited[z][x][y] = 1;
                } else if (arr[z][x][y] == 0) {
                    allRipe = false; // 익지 않은 토마토가 있음
                }
            }
        }
    }

    if (allRipe) {
        cout << 0 << '\n';
        return 0;
    }

    bfs();

    for (int z = 0; z < h; z++) {
        for (int x = 0; x < n; x++) {
            for (int y = 0; y < m; y++) {
                if (arr[z][x][y] == 0) {
                    cout << -1 << '\n'; // 익지 않은 토마토가 남아 있으면 -1 출력
                    return 0;
                }
                maxDays = max(maxDays, dis[z][x][y]);
            }
        }
    }

    cout << maxDays << '\n'; // 최대 날짜 출력
    return 0;
}

---

코드 설명

위 코드는 BFS를 사용하여 3차원 공간에서 모든 토마토가 익는 최소 날짜를 계산합니다.

• 입력 처리:
  • 상자의 상태를 3차원 배열 `arr`에 저장하고, 익은 토마토의 위치를 큐에 추가합니다.
  • 익지 않은 토마토가 없는 경우 바로 0을 출력합니다.
• BFS 탐색:
  • 큐에서 익은 토마토의 위치를 꺼내 주변 6방향을 탐색하며 익지 않은 토마토를 익게 만듭니다.
  • `dis` 배열을 사용해 각 위치까지 걸린 최소 날짜를 기록합니다.
• 결과 처리:
  • 모든 토마토가 익었는지 확인합니다. 익지 않은 토마토가 있으면 -1을 출력합니다.
  • 모든 토마토가 익었다면 `dis` 배열에서 최대 값을 출력합니다.

시간 복잡도 분석:

• BFS 탐색: O(M × N × H).
• 최대 크기가 100 × 100 × 100이므로 효율적으로 동작합니다.

---

결과

다음은 입력 예시와 출력 결과입니다:

입력:
5 3 1
0 -1 0 0 0
-1 -1 0 1 0
0 0 0 0 0

출력:
4

모든 토마토가 익는 데 걸리는 최소 날짜를 정확히 계산하여 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!