BOJ [7576] 토마토

 

 

https://www.acmicpc.net/problem/7576

 

 

1. 분류

BFS

 

 

 

2. 풀이

 

모든 토마토를 익힐 때까지 며칠이나 걸릴지를 구하는 문제.

 

익은 토마토는 주변 상하좌우의 토마토를 익혀버린다. 좀비도 아니고...;

 

큐에 넣은 인접 토마토들이 다 빠져나온 순간을 하루가 지난 것으로 설정하였다.

 

 

 

3. 소스코드

#include <cstdio>
#include <queue>

using namespace std;

int map[1000][1000];
const int dy[4] = { -1, 0, 1, 0 };
const int dx[4] = { 0, 1, 0, -1 };

int main()
{
    int m, n, day = 0;
    bool isPossible = false, isFull = true;
    queue<pair<int, int>> q;
    scanf("%d %d", &m, &n);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &map[i][j]);
            
            if (map[i][j] == 1) {
                isPossible = true;
                q.push({ i, j });
            } else if (map[i][j] == 0) {
                isFull = false;
            }
        }
    }

    // 익은 토마토가 하나도 없으면 바로 종료
    if (!isPossible) {
        printf("-1\n");

    // 모든 토마토가 익은 상태면 바로 종료
    } else if (isFull) {
        printf("0\n");

    } else {
        while (!q.empty()) {
            
            int size = q.size();

            for (int loop = 0; loop < size; loop++) {
                int y = q.front().first;
                int x = q.front().second;

                q.pop();

                // 현재 좌표의 위, 오른쪽, 아래, 왼쪽 순으로 검사
                for (int i = 0; i < 4; i++) {
                    // out of index 방지
                    if (y + dy[i] < 0 || y + dy[i] >= n || x + dx[i] < 0 || x + dx[i] >= m)
                        continue;

                    // 목표가 익지 않은 토마토면 익은 것으로 설정하고 큐에 삽입
                    if (map[y + dy[i]][x + dx[i]] == 0) {
                        map[y + dy[i]][x + dx[i]] = 1;
                        q.push({ y + dy[i], x + dx[i] });
                    }
                }
            }

            day++;
        }

        // 모든 토마토가 익었는지 확인
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 0) {
                    isPossible = false;
                    printf("-1\n");
                    return 0;
                }
            }
        }

        printf("%d\n", day - 1);
    }

    return 0;
}