7576. 토마토

#include <queue>
#include "bits/stdc++.h"
 
using namespace std;
 
int vx[] = {1, -1, 0, 0};
int vy[] = {0, 0, 1, -1};
 
int main()
{
    int M,N;
    scanf("%d %d", &M, &N);
 
    int tomatos[1001][1001];
 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            scanf("%d", &tomatos[i][j]);
 
    int board[1001][1001];
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            board[i][j] = -1;
        }
    }
 
    queue<int> tomatoX;
    queue<int> tomatoY;
 
    int startX, startY;
    bool isDecided = false;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
            if (tomatos[i][j] == 1)
            {
                startX = j;
                startY = i;
                tomatoX.push(startX);
                tomatoY.push(startY);
                board[startY][startX] = 0;
            }
    }
 
    while (!tomatoX.empty())
    {
        int x = tomatoX.front(), y = tomatoY.front();
        tomatoX.pop();
        tomatoY.pop();
        for (int i = 0; i < 4; i++)
        {
            int nextX = x + vx[i];
            int nextY = y + vy[i];
            if (nextX >= 0 && nextX < M 
            && nextY >= 0 && nextY < N 
            && board[nextY][nextX] == -1 
            && tomatos[nextY][nextX] == 0)
            {
                board[nextY][nextX] = board[y][x] + 1;
                tomatoX.push(nextX);
                tomatoY.push(nextY);
            }
        }
    }
 
    int max = 0;
 
    for(int i = 0 ; i < N; i++) {
        for(int j = 0; j < M; j++) {
            if(tomatos[i][j] == 0 && board[i][j] == -1) {
                printf("-1\n");
                return 0;
            }
            max = std::max(max, board[i][j]);
        }
    }
    printf("%d\n", max);
    return 0;
}

전형적인 BFS문제이다. 그래서 BFS를 알지 못하면 풀지 못할 것이고(잘하는 사람이라면 다른 푸는 방법을 알지도...) 알고 있다면 풀 수 있는 문제라고 생각된다. 하지만 여기서 주의해야할 점이 문제를 잘 봐야한다는 것이다.

문제를 보면 익은 토마토가 주어지고 그 토마토를 기준으로 양 옆, 위 아래로 익지 않은 토마토가 있으면 그 토마토들을 하루 지난다음에 익게하는 것이다. 하지만 여기서 주의해야할 점이 익은 토마토는 여러개가 주어질 수 있다는 것이다. 그래서 처음에 bfs를 이용하기 위해서 queue에 넣는 상황에서 익은 토마토들을 전부 넣어주어야 한다. 그러면 기초적인 준비로 bfs를 시작할 준비가 끝나게 된다.

그렇다면 다음 단계인 문제의 답을 알기위한 며칠이 지나면 토마토가 다 익는지를 알기위한 단계이다. 토마토 창고 안에 담겨있는 토마토들이 모두 익을 수 있다면 제일 늦게 익는 토마토가 만들어지는 날이 답에 맞는 날이 될 것이다. 이 날을 알기위해서는 익은 토마토를 기준으로 양옆,위아래를 거쳐서 익는 토마토들이 익은 토마토에서 가장 먼 토마토에 도달하는데 걸리는 날의 최소의 일수를 알아야 한다. 

이를 위해서 board라는 배열을 하나 선언해주고 최초에 익은 토마토들이 담겨있는 위치를 0로 만들어준다. board가 하는 일은 다음 토마토들이 익는 최소의 날수를 적어놓는 메모장 역할을 한다고 이해하면 쉽게 이해가 된다. 처음에 익은 토마토가 담겨있는 위치를 0으로 해준 이유는 아직 날짜가 지나지 않았기 때문이다.

그 이후는 bfs에 알맞는 조건식을 넣어주면 된다. 여기서 사용된 조건은 처음에 배열의 크기를 받았는데 그 크기에 벗어나기 않으면서 board의 값이 -1이고 토마토들이 담겨있는 창고가 0일때만 실행해주도록 하였다. 그 이유는 board값이 -1로 되어있으면 아직 익은 토마토가 아니라는 뜻이기 때문이다.

마지막으로 board에 저장되어있는 일수를 가지로 최대값을 찾으면 우리가 원하는 답을 구할 수 있다. 하지만 이때 주의해야할 점이 토마토가 들어있지 않아서 발생할 수 있는 모든 토마토가 익지 않을 수 있는 경우의 수이다. 이를 표현해주기 위해서 board값을 검사하면서 익지 않은 토마토가 있다면, 즉 토마토 창고에 토마토는 들어있지만 board의 값이 -1인 경우에, -1을 출력해주고 실행을 마친다. 이 경우가 아니라면 board에 적힌 일수 중 최대값을 반환하면 된다.