[BOJ/C++] 토마토(7576번)

1. 개요

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

1-1. 설명

철수의 토마토 농장에는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자 칸에 하나씩 넣어 창고에 보관한다.

토마토가 저장될 박스

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게된다. 하나의 토마토에 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선에 있는 토마토들에게는 영향을 주지 못하고, 토마토 혼자 저절로 익는 경우는 없다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고싶어 한다.

 

토마토를 창고에 보관하는 격자모양 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 여기서 일부 칸에는 토마토가 들어있지 않을수도 있다. 

1-2. 제한 사항

 - 첫 줄에는 상자의 크기를 나타내는 두 정수 M, N이 주어지며, M은 가로 칸의 수, N은 세로 칸의 수를 나타냄

 - M과 N은 2 이상 1,000이하 자연수

 - 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어짐

 - 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어지며, 하나의 줄에는 상자 가로줄에 들어있는 토마토 상태가 M개의 정수로 주어짐

 - 1은 익은 토마토, 0은 익지 않은 토마토, -1은 토마토가 들어있지 않은 칸

 - 토마토가 모두 익을때까지의 최소 날짜 출력, 여기서 모든 토마토가 익어있는 상태면 0을 출력, 토마토가 익지 못하는 상황이면 -1 출력

---

2. 구현

2-1. 풀이

그래프에서 BFS를 이용하여 구현하면 된다. 단순히 BFS를 여러 번 실행하면 시간 초과에 걸리게 되므로, 어떤 식으로 접근해야 할지 잘 생각해야 한다. 

처음 구현할 때는 1을 뽑아 각각 BFS를 실행하고 토마토가 익을 수 있는 날짜 중 적은 날짜를 선택하게끔 하였다. BFS가 1의 개수만큼 돌아야하므로 시간 초과가 나버렸다. 여기서, 각각 BFS를 실행시키는 것이 아닌 BFS 실행을 위한 Queue에 1인 좌표를 모두 저장하여 그 Queue를 이용해 BFS를 한 번만 실행하고 결과를 내면 시간 초과에 걸리지 않게 된다. 

2-2. 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

#define MAX_BOXES_CNT 1001

using namespace std;

bool CanTomatoesBeRiped(int N, int M); // 안익은 토마토 존재 유무
void BFS(int N, int M);

int boxes[MAX_BOXES_CNT][MAX_BOXES_CNT]; // 격자 모양 박스
int cost[MAX_BOXES_CNT][MAX_BOXES_CNT]; // 토마토가 익어가는 날짜
bool visited[MAX_BOXES_CNT][MAX_BOXES_CNT]; // 방문 여부

queue<pair<int, int>> que;

int dirX[4] = { 0, 0, -1, 1 };
int dirY[4] = { 1, -1, 0, 0 };

int result = 0;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int M, N;
    vector<pair<int, int>> tomatoes;

    cin >> M >> N;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> boxes[i][j];
            if (boxes[i][j] == 1) 
                que.push({ i, j });
                // 토마토를 모두 queue에 저장해 BFS가 한 번만 진행되게끔 구현
        }
    }

    BFS(N, M);

    if (!CanTomatoesBeRiped(N, M)) result = -1;
    // 안익은 토마토가 존재하면 -1

    cout << result;
}

bool CanTomatoesBeRiped(int N, int M) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (cost[i][j] == 0 && boxes[i][j] == 0) return false;
            // 익지 않은 토마토가 존재할 때
        }
    }
    return true;
}

void BFS(int N, int M) {
    while (!que.empty()) {
        int curX = que.front().first;
        int curY = que.front().second;

        que.pop();

        for (int i = 0; i < 4; i++) {
            int nextX = curX + dirX[i];
            int nextY = curY + dirY[i];

            if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= M) continue;
            if (visited[nextX][nextY] || boxes[nextX][nextY] != 0) continue;
            // 이미 방문했거나, 토마토가 익었을 때

            cost[nextX][nextY] = cost[curX][curY] + 1;
            if (result < cost[nextX][nextY]) result = cost[nextX][nextY];
            visited[nextX][nextY] = true;
            que.push({ nextX, nextY});
        }
    }
}