[알고리즘][12][백준_7576][c++] - 토마토

 

 

---

문제 이해

토마토 문제에서는 각 박스내에 3가지 상태가 존재한다.  익은 토마토(1), 안익은 토마토(0), 비어있는 칸(-1).

 

주의할 점은 익은 토마토는 자신의 상하좌우에 위치한 토마토만을 익힐 수 있고, 비어있는칸이 존재할 수 있기때문에, 문제의 예제2 처럼 모든  토마토를 전부 익힐 수 없는 상황이 주어질 수도 있다는 점을 고려해야한다.

 

 

---

알고리즘 설계

문제에서 주어진 예제3의 경우를 시각화했을 때의 모습이다.

간단하게 생각해보면,

 

1. 현재 익은토마토(1)의 상하좌우의  토마토들의 상태를 1로 바꾼다.

2. 현재 익은토마토들 주변에 익힐수 있는 토마토가 없을 경우 종료 / 아닐 경우 1 반복

 

로 표현할수 있다. 

 

그런데 현재 익은 토마토의 개수는 매번 달라지므로 일반적인 재귀함수로 표현하기는 힘들것 같다.

 

 

위 그림을 보면 비어있지 않은 칸을 제외한 모든 토마토들의 연결 관계가 표현되어있다.

 

즉 이 토마토들의 관계를 그래프로 생각하고 익은 토마토들부터 시작해서 자신과 연결된 토마토들을 익히고 이 과정을 반복하면서 모든 토마토를 익혔을때의 횟수를 체크하면 될것같다.

 

즉 너비 우선 탐색 BFS를 이용하여 현재 익은 토마토들을 큐에 넣고, 다음에 익힐수 있는 토마토들을 새로운 큐에 넣고, 새로운 큐에 넣어진 토마토들이 익힐 수 있는 토마토들을 또 새로운 큐에 넣어주고...

 

이 과정을 반복하면 될것이다.

 

대신 주의해야 할 점은,

1. 이미 익은 토마토 혹은 비어있는 칸으로는 이동해서는 안되고

2. 현재 익혀야할 전체 토마토 개수를 저장해두고  모든 BFS가 끝났을 때 모든 토마토를 익혔는지 확인 할 필요가 있다.

 

 

// 그래프 이론에서 너비우선 탐색 - pair를 속성으로 가지는 queue를 이용함.
// 2차원 배열을 사용해서 각 지점들의 상태 표현

#include <iostream>
#include <vector>
#include <utility>
#include <queue>

using namespace std;

int M,N;
int input[1001][1001];
int maximum = -1;
int leftCount = 0; // 현재 더 익혀야할 토마토수

queue<pair<int, int> > now_queue;
queue<pair<int, int> > next_queue;


void check_around_tomato(int i, int j){
    // (i,j) 주변에 자신이 익힐수 있는, 상태가 0인 토마토들을 next 큐에 pair 형태로 넣어준다. 
    if(i != N-1){ // down
        if(input[i+1][j] == 0){
            next_queue.push(make_pair(i+1,j));
            input[i+1][j] = 1;
            leftCount--;
        }
    }
    if(i != 0){ // up
        if(input[i-1][j] == 0){
            next_queue.push(make_pair(i-1,j));
            input[i-1][j] = 1;
            leftCount--;
        }
    }
    if(j != M-1){ // right
        if(input[i][j+1] == 0){
            next_queue.push(make_pair(i,j+1));
            input[i][j+1] = 1;
            leftCount--;
        }
    }
    if(j != 0){ // left
        if(input[i][j-1] == 0){
            next_queue.push(make_pair(i,j-1));
            input[i][j-1] = 1;
            leftCount--;
        }
    }
}

void tomato(){
    now_queue = next_queue;
    while(next_queue.size() > 0){
        next_queue.pop();
    }

    int len;
    len = now_queue.size();
    if(len > 0){
        for(int i=0;i<len; i++){
            check_around_tomato(now_queue.front().first, now_queue.front().second);
            now_queue.pop();
        }
        maximum++;
        tomato();
    }
}

int main(){

    cin >> M;
    cin >> N;
    int tmp;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            cin >> tmp;
            input[i][j] = tmp;
            if(tmp == 1){
                next_queue.push(make_pair(i,j));
            }
            if(tmp == 0){
                leftCount++;
            }
        }
    }

    tomato();
    if(leftCount > 0){
        cout << -1;
    }
    else{
        cout << maximum;
    }
}