1 문제

BFS를 이용해 완전 탐색을 하되, Starting Point가 여러 지점이고, 빈 지역이 있는 문제

2 Idea

입력된 지도 정보를 BFS에서 업데이트하도록 구현해 visit을 따로 선언하지 않음

BFS에 들어가기 전에 탐색할 필요가 없는지를 확인해 없다면 return 0

BFS 이후에 0(익지 않음)이 남아있는지 확인해 있다면 return -1

3 Code

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

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

typedef enum{
    EMPTY       = -1,
    NOT_RIPE    = 0,
    RIPE        = 1,
} tomato;

typedef struct{
    int i;
    int j;
    int time;
} pos;

const std::vector<std::vector<int>> DIRECTION = {
    {1, 0},
    {-1, 0},
    {0, 1},
    {0, -1},
};

int CalulateRipeDay(std::vector<std::vector<tomato>> v, const int N, const int M){
    //check all tomato is rippen
    bool isAllTomatoRippen = true;
    for (int i=0; i<N; ++i){
        for (int j=0; j<N; ++j){
            if (v[i][j] == NOT_RIPE){
                isAllTomatoRippen = false;
            }
        }
    }

    if (isAllTomatoRippen){
        //all tomato is rippen
        //  -> return 0
        return 0;
    }
    
    //make queue and push ripe point
    std::queue<pos> q;

    for (int i=0; i<N; ++i){
        for (int j=0; j<M; ++j){
            if (v[i][j] == RIPE){
                q.push({i, j, 0});
            }
        }
    }

    //BFS
    int ripeDay = 0;
    while(!q.empty()){
        const pos current = q.front();
        q.pop();

        const int i = current.i;
        const int j = current.j;
        const int time = current.time;

        for (const auto& dir : DIRECTION){
            const int i_new = i+dir[0];
            const int j_new = j+dir[1];

            if ((i_new >= N) || (j_new >= M) || (i_new < 0) || (j_new < 0)){
                //out of v
                continue;
            }
            else if (v[i_new][j_new] == RIPE){
                //already ripe
                //  -> continue
                continue;
            }
            else if (v[i_new][j_new] == EMPTY){
                //empty
                //  -> continue
                continue;
            }
            else{
                //not ripe

                v[i_new][j_new] = RIPE;
                q.push({i_new, j_new, time+1});

                ripeDay = time+1;
            }

        }
    }

    //check not ripe tomato after BFS
    for (int i=0; i<N; ++i){
        for (int j=0; j<M; ++j){
            if (v[i][j] == NOT_RIPE){
                return -1;
            }
        }
    }

    return ripeDay;
}

int main(){
    int N = 0;
    int M = 0;

    std::cin >> N >> M;
    std::vector<std::vector<tomato>> v(N, std::vector<tomato>(M, EMPTY));

    for (int i=0; i<M; ++i){
        for (int j=0; j<N; ++j){
            int temp;
            std::cin >> temp;

            v[j][i] = static_cast<tomato>(temp);
        }
    }

    std::cout << CalulateRipeDay(v, N, M) << std::endl;

    return 0;
}