7576번 : 토마토

Backjoon Online Judge 

"7576번 : 토마토" 문제입니다.

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

'7576번 : 토마토' 문제의 경우 보자마자 BFS가 떠올랐을 정도로 BFS의 기본과 같은 문제라 생각됩니다.

문제에 대한 설명은 코드 설명과 함께 진행하면 이해가 빠를 것 같습니다.

문제 및 코드 설명입니다.

먼저 토마토 상자의 상태를 저장하기 위해 2차원 배열로 상자를 만들었습니다.

BFS를 사용하기 위해 큐를 pair로 선언하여 x좌표, y좌표를 저장했습니다.

이후 q에서 익은 토마토를 꺼내어 주변 토마토를 익게 합니다. 이때 익는 토마토는 상자에 익은 날짜를 저장합니다.

익은 토마토가 다른 토마토를 익게 할 때마다 익은 토마토의 날짜에서 1씩 더한다면

마지막 익은 토마토는 최종 날짜를 저장하게 되고 그 날짜를 출력해 주면 됩니다.

다만 출력하기 전 상자를 확인하여 익지 않은 토마토가 있는지 확인하고, 있다면 -1을 출력합니다.

(추가적으로 side[4] 배열은 특정 토마토의 상하좌우를 확인하기 위해 작성하였습니다.

 일일히 상하좌우를 지정하기 불편하여 간단한 skill을 이용하였고, 코드를 따라가면 자연스럽게 이해되리라 생각합니다.)

코드는 C++로 작성하였습니다.

(단, 큐를 pair을 이용해 구현하여 C++ 11 이상에서만 정상작동 합니다.

 C++ 11 이하에서 작동되기를 원하시면 큐를 pair로 구현하는 대신 2개를 만들면 됩니다.)

#include <iostream>
#include <queue>
 
#define Max 1000
 
using namespace std;
 
int main() {
    int M, N, x, y, tx, ty;
    int box[Max][Max] = { 0, };
    int result = 0;
    queue<pair<int,int>> q;
 
    cin >> M >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> box[i][j];
            if (box[i][j] == 1) {
                q.push({ i,j });
            }
        }
    }
 
    int side[4] = {1, 0, -1, 0};
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        
        if (box[x][y] == 2 + result)
            result++;
        
        for (int i = 0; i < 4; i++) {
            tx = x - side[i];
            ty = y - side[3 - i];
            if (0 <= tx && tx < N && 0 <= ty && ty < M) {
                if (box[tx][ty] == 0) {
                    box[tx][ty] = 2 + result;
                    q.push(make_pair(tx, ty));
                }
            }
        }
        q.pop();
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (box[i][j] == 0) {
                result = -1;
                break;
            }
        }
    }
    cout << result << endl;
}