백준온라인저지(BOJ)/#7576/BFS/토마토

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

7576번: 토마토

토마토 문제이다.

토마토는 처음에 특정 좌표만 익어있고, 이후 하루 지날 때마다 익은 토마토를 기점으로 인접 좌표의 토마토들로 익은 것이 번져나간다. 

토마토가 모두 익을 때까지 걸리는 최소 날짜는 즉, 익은 토마토들을 기점으로 BFS를 시작했을 때 가장 멀리 떨어진 거리만큼이 될 것이다.

알고리즘 설계는 아래와 같이 할 수 있다. BFS를 사용하기 적합한 이유로는 BFS는 인접한 노드부터 탐색을 하므로 days를 갱신해주기만 하면 저 최소 날짜를 구하기 용이하기 때문이다. 

한 가지 요령은 int days를 놓고, BFS 를 실행하면서 시작점에서 인접 좌표가 조건을 만족하여 익는 토마토로 마킹해줄 때 days 를 최대값으로 갱신해주면 가장 큰 거리값을 days에 갱신할 수 있다. 

//1. 좌표별 상태를 나타내는 map[][]을 설정한다. map[i][j]에는 토마토 밭의 상태

//2. 좌표별 일수를 계산하는 cost[][]를 설정한다. cost[i][j]에는 토마토가 익기까지 걸리는 일수가 들어간다

//3. 토마토가 심어져있는 좌표를 기점으로 BFS를 실행하여, 인접 좌표들부터 1로 마킹하여 토마토를 익힌다.

//4. BFS를 모두 실행한 후 토마토가 최대로 익은 좌표 map에 대해 check tomato function으로 체크한다.

---

[구현코드]

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

using namespace std;
vector<vector<int>> map;
vector<vector<int>> cost;
int M, N, days; // M은 가로, N은 세로를 의미

bool check_tomato(){
    bool flag = true;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            if(map[i][j] == 0){
                return false;
            }
        }
    }
    return flag;
}

void bfs(vector<pair<int,int>> vec){
    queue<pair<int, int>> q;
    const int dy[] = {-1, 1, 0, 0};
    const int dx[] = {0, 0, -1, 1};
    for(int k = 0; k < vec.size(); k++){
        q.push(vec[k]);
    }
    
    days = 0; // 최대값을 갱신하기 위한 days 선언
    while(!q.empty()){
        pair<int, int> here = q.front();
        q.pop();
        // 상하좌우로 순회하면서, 즉 인접 좌표들을 순회하면서 탐색함
        for(int m = 0; m < 4; m++){
            int next_y = here.first + dy[m];
            int next_x = here.second + dx[m];
            if(next_y>=0 && next_y < N
               && next_x >= 0 && next_x < M
               && map[next_y][next_x] != -1
               && map[next_y][next_x] == 0){
                cost[next_y][next_x] = cost[here.first][here.second] + 1;
                map[next_y][next_x] = 1;
                days = max(days, cost[next_y][next_x]); // days에 최대값을 계속 갱신해준다.
                q.push(make_pair(next_y, next_x));
            }
        }
    }
}

int main(){
    vector<pair<int, int>> start;
    cin>>M>>N;
    map.resize(N,vector<int>(M,0));
    cost.resize(N,vector<int>(M,0));
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            int a;
            cin>>a;
            map[i][j] = a;
            if(map[i][j] == 1){
                start.push_back(make_pair(i,j));
            }
        }
    }
    bfs(start);
    if(check_tomato()){
        cout<<days<<'\n';
    }
    else{
        cout<< -1 <<'\n';
    }
    return 0;
}

휴우.. 코드가 길구나.

써놓고 보니까 괜찮네.