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

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

---

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

문제 설명:

상자에 보관된 토마토가 모두 익을 때까지 걸리는 최소 날짜를 계산하세요. 익은 토마토는 상하좌우로 하루에 한 칸씩 익지 않은 토마토에 영향을 줍니다.

입력 조건:

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

출력 조건:

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

---

문제 해결 코드

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

int n, m;
int arr[1001][1001]; // 토마토 상태 저장
int dist[1001][1001]; // 날짜 계산
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

queue<pair<int, int>> q;

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

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 1 && nx <= m && ny >= 1 && ny <= n) {
                if (arr[nx][ny] == 0) {
                    arr[nx][ny] = 1;
                    dist[nx][ny] = dist[x][y] + 1;
                    q.push({nx, ny});
                }
            }
        }
    }
}

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

    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 1) {
                q.push({i, j}); // 익은 토마토의 위치 저장
            }
        }
    }

    bfs();

    int maxDays = 0;
    bool allRipe = true;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (arr[i][j] == 0) {
                allRipe = false; // 익지 않은 토마토가 남아 있음
            }
            maxDays = max(maxDays, dist[i][j]);
        }
    }

    if (allRipe) {
        cout << maxDays << '\n';
    } else {
        cout << -1 << '\n';
    }

    return 0;
}

---

코드 설명

위 코드는 BFS를 사용하여 익은 토마토가 익지 않은 토마토를 익히는 과정을 시뮬레이션합니다.

• 입력 처리:
  • 토마토의 상태를 `arr` 배열에 저장합니다.
  • 익은 토마토의 위치를 큐에 추가합니다.
• BFS 탐색:
  • 큐에서 익은 토마토의 위치를 꺼내고, 상하좌우의 토마토를 익게 만듭니다.
  • `dist` 배열을 사용해 익는 데 걸린 날짜를 기록합니다.
• 결과 처리:
  • 모든 토마토가 익었는지 확인합니다. 익지 않은 토마토가 남아 있으면 -1을 출력합니다.
  • 모든 토마토가 익었다면 최대 날짜를 출력합니다.

시간 복잡도 분석:

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

---

결과

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

입력:
6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1
0 0 0 0 0 0

출력:
8

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

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