# 7576. 토마토

관련 알고리즘 : BFS

 

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

7576번: 토마토

---

문제 풀이

며칠이 지나면 토마토들이 익는 지 "최소 일수"를 구해야 하므로 bfs를 사용한다.

 

1. 토마토들의 상태(-1, 0, 1)을 배열에 저장
2. 익은 토마토들을 큐에 넣기
3. 익은 토마토들 상하좌우 토마토들 방문 여부 확인
4. 안 익은 토마토가 존재 시, day++ 하여 날짜를 증가시키고 익었다 처리
5. 해당 토마토를 큐에 넣기
6. 위의 과정 반복

---

C++ 코드

#include <iostream>
#include <queue>

using namespace std;

const int MAX = 1001;
int M, N;

int box[MAX][MAX]; // 토마토 상태 받는 배열
bool check[MAX][MAX]; // 방문 여부 체크
int day[MAX][MAX]; // [i][j]칸 토마토가 익는 날짜
int dy[] = { 0,0,1,-1 };
int dx[] = { 1,-1,0,0 };
queue<pair<int, int>> q;

void BFS() {
    while (!q.empty()) { // 큐 내 토마토(익은 토마토) pop
        int y = q.front().first;
        int x = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++) { // 상하좌우 확인하기
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (ny < 0 || nx < 0 || ny >= N || nx >= M) // 상자 밖인 경우
                continue;

            if (box[ny][nx] == 0 && check[ny][nx] == 0) { // 상자 내에 있고, 익지 않은 토마토일 때
                check[ny][nx] = true; // 방문 처리
                q.push(make_pair(ny, nx)); // queue에 넣기
                day[ny][nx] = day[y][x] + 1;
            }
        }
    }

}

int main() {
    cin >> M >> N;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> box[i][j];
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (box[i][j] == 1) { // 익은 토마토라면
                q.push(make_pair(i, j)); // queue에 넣기
            }
        }
    }
    BFS();

    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (box[i][j] == 0 && day[i][j] == 0) { //익지 않은 토마토 있고, 방문한 적 없을 때
                cout << -1; // -1 출력
                return 0;
            }
        }
    }

    int ans = -1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (day[i][j] > ans) { // 익은 날짜들 중 최대값 출력
                ans = day[i][j];
            }
        }
    }
    cout << ans;

}