[Baekjoon]7576번 - 토마토

 

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

7576번: 토마토

 

 

1. 토마토가 이미 모두 익어있는 상태를 체크 - 익은토마토(=ripe) + 토마토가없는곳(=no) 의 합이 N*M 전체개수와 같으면 0 출력 후 종료

2. BFS를 이용해 맨 처음 배열 전체를 보고 익어있는토마토 (=1) 의 상,하,좌,우가 0이면 큐에다 넣어두기

3. 해당 큐의 크기만큼 큐의 front에 있는 익은토마토에 대해서도 또 상,하,좌,우로 0인 곳을 1로바꿔주며 큐에 push하는걸 반복. 1회 반복할때마다 result++ 해줌

4. 1~3을 완료했는데도 tomato에 익지않은토마토 (=0)이 있다면 result = -1

 

---

코드

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

int result = 0;
int dx[] = {0, 0, 1, -1}; //상 하 우 좌
int dy[] = {1, -1, 0, 0};
int no = 0;

void alreadyRipe(vector<vector<int>> tomato, int M,int N){
    int ripe = 0; //익은 토마토
      for(int i=0;i<N;i++){
        ripe += count(tomato[i].begin(), tomato[i].end(), 1);
        no += count(tomato[i].begin(), tomato[i].end(), -1);
    }
    if(ripe == N*M || ripe+no == N*M) {result=0; return;} //저장될때부터 모든 토마토 익어있는 상태
}
void noRipe(vector<vector<int>> tomato, int M,int N){
    int xx = 0;
    for(int i=0;i<N;i++){
        xx += count(tomato[i].begin(), tomato[i].end(), 0);
    }
    if(xx > 0) result = -1;
}

void BFS(vector<vector<int>> &tomato, int M, int N){
    
    queue<pair<int, int>> q;
    for(int i=0;i<N;i++)for(int j=0;j<M;j++) if(tomato[i][j] == 1) q.push(make_pair(i, j));

    while(1){
    
        int q_size = q.size();
        while(q_size--){
        
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
        
            for(int k=0;k<4;k++){
                int nx = x + dx[k];
                int ny = y + dy[k];
                
                if(nx >= 0 && ny >= 0 && nx < N && ny < M){
                    if( tomato[nx][ny] == 0) {
                        q.push(make_pair(nx, ny));
                        tomato[nx][ny] = 1;
                    }
                }
            }
        }
        if(q.empty()) break;
        result++;
    }
}

int main(int argc, const char *argv[])
{
    int M,N;
    cin >> M >> N;//M이 가로 N이 세로
    int inp = 0;
    vector<vector<int>> tomato(N, vector<int>(M));
    for(int i=0;i<N;i++)for(int j=0;j<M;j++){cin >> inp; tomato[i][j]=inp; }
    
    alreadyRipe(tomato, M,N); //토마토가 이미 익어있는 상태 확인
    BFS(tomato, M, N);
    noRipe(tomato, M, N); //토마토가 모두 익지 못하는 상황 확인

    cout << result;
    return 0;
}

 

 

이전에 풀었던 보물섬 문제랑 비슷한 유형이었다.

2022.01.17 - [study/Baekjoon] - [Baekjoon] 2589번 보물섬

[Baekjoon] 2589번 보물섬

 

 

vector를 함수 인자로 넘길 때 &를 실제로 써본 건 처음이었다. main에서 선언한 tomato벡터를 BFS에서 분명 업데이트했는데, 다시 main에서 예외를 체크하려고 보니까 tomato의 값이 처음 초기화 상태 그대로였다. 왜 업데이트되지 않은 거지? 하고 보니까 &를 사용하지 않아서 값만 넘겨주는 방식이어서 그랬다. BFS함수 선언부에 &를 넣어주니 해결됐다.

사용안함  - 값만 넘김(call by value) 복사	& 사용 - call by reference 공유
void func(vector v){}	void func(vector &v){}