백준 7576번 : 토마토

• 분류: 그래프

코드(방법 1)

#include <iostream>
#include <queue>
using namespace std;

class Tomato {
public :
    int status;
    int visited = false;
    Tomato* left;
    Tomato* up;
    Tomato* right;
    Tomato* down;
    Tomato() {};
    Tomato(int status): status(status) {}
};

int main() {
    int m, n;
    cin >> m >> n;
    Tomato tomatoes[n][m];
    queue<Tomato> defaultQueue;

    bool existZero = false;
    bool existOne = false;
    for(int i=0 ; i<n ; i++) {
        for(int j=0 ; j<m ; j++) {
            int input;
            cin >> input;
            tomatoes[i][j] = Tomato(input);
            if(input==0) existZero = true;
            if(input==1) existOne = true;
        }
    }
    if(!existZero) {
        cout << 0;
        return 0;
    }
    if(!existOne) {
        cout << -1;
        return 0;
    }

    for(int i=0 ; i<n ; i++) {
        for (int j=0; j < m; j++) {
            if(i==0 || tomatoes[i-1][j].status==-1) tomatoes[i][j].up = nullptr;
            else tomatoes[i][j].up = &tomatoes[i-1][j];

            if(i==n-1 || tomatoes[i+1][j].status==-1) tomatoes[i][j].down = nullptr;
            else tomatoes[i][j].down = &tomatoes[i+1][j];

            if(j==0 || tomatoes[i][j-1].status==-1) tomatoes[i][j].left = nullptr;
            else tomatoes[i][j].left = &tomatoes[i][j-1];

            if(j==m-1 || tomatoes[i][j+1].status==-1) tomatoes[i][j].right = nullptr;
            else tomatoes[i][j].right = &tomatoes[i][j+1];

            if(tomatoes[i][j].status==1) defaultQueue.push(tomatoes[i][j]);
        }
    }

    int day=0;
    queue<Tomato> tempQueue;
    while(!defaultQueue.empty()) {
        if(defaultQueue.front().up != nullptr) {
            if(!defaultQueue.front().up->visited) {
                defaultQueue.front().up->status=1;
                defaultQueue.front().up->visited = true;
                tempQueue.push(*defaultQueue.front().up);
            }
        }
        if(defaultQueue.front().down != nullptr) {
            if(!defaultQueue.front().down->visited) {
                defaultQueue.front().down->status=1;
                defaultQueue.front().down->visited = true;
                tempQueue.push(*defaultQueue.front().down);
            }
        }
        if(defaultQueue.front().left != nullptr) {
            if(!defaultQueue.front().left->visited) {
                defaultQueue.front().left->status=1;
                defaultQueue.front().left->visited = true;
                tempQueue.push(*defaultQueue.front().left);
            }
        }
        if(defaultQueue.front().right != nullptr) {
            if(!defaultQueue.front().right->visited) {
                defaultQueue.front().right->status=1;
                defaultQueue.front().right->visited = true;
                tempQueue.push(*defaultQueue.front().right);
            }
        }
        defaultQueue.pop();
        if(defaultQueue.empty()) {
            if(tempQueue.empty()) {
                for(int i=0 ; i<n ; i++) {
                    for (int j = 0; j < m; j++) {
                        if(tomatoes[i][j].status==0) {
                            cout << -1;
                            return 0;
                        }
                    }
                }
                break;
            }
            day++;
            defaultQueue = tempQueue;
            tempQueue = queue<Tomato>();
        }
    }
    cout << day;
}

• 코멘트
  
  마치 상하좌우로 링크가 있는 node처럼 생긴 Tomato 객체를 만든다.
  입력에 따라 토마토 객체의 초기 상태를 설정하고 배열에 넣어 준 후, 익은 토마토는 queue에 넣어 준다.
  만약 초기 상태에서 모든 토마토가 다 0이나 -1이면 답은 -1이고, 모든 토마토가 1이면 답은 0이다.
  여기까지 하면 0일차 세팅이 끝나고, 이제 queue에서 하나씩 뽑아서 상하좌우를 익혀 준다. 이때 새로 익은 토마토들은 따로 다른 queue에 넣어 놨다가, 해당 일차가 끝나면(=defaultQueue가 비면) 새로 익은 토마토들을 defaultQueue에 옮겨 주는 식으로 한다.
  
  defaultQueue가 비었을 때, tempQueue도 비어있으면
  1. 안 익은 토마토가 있으면 얘는 접근 불가능한 토마토다. 답은 -1
  2. 토마토가 다 익어있으면 이날 아무것도 한 게 없다는 뜻이고 이는 전날에 이미 모든 토마토가 익었다는 뜻이 된다. 따라서 바로 break해서 답을 출력해준다.