[백준 7576] 알고리즘 85일차 : 토마토

www.acmicpc.net/problem/7576

7576번: 토마토

C++ BFS

토마토 농장에 갇혔다가 겨우 탈출함.

진짜.

...세상 기쁘다

문제를 설명할 기력은 없네요. 대충 토마토 빨리 익히는 게임이라고 생각하면 됩니다.

 

접근방법

BFS .. 과연.. 익은 토마토를 큐에 넣습니다.

다 익었는지 체크 -> 익었으면 0 출력

반복문 들어감(큐가 비어있지 않으면 계속 돌아가는 반복문)

-> 큐에서 팝하고 방문했다고 체크, 인접한 토마토들 큐에 넣기

     전날 큐에 넣은 토마토를 다 뺐으면 cnt++

다 익었는지 체크 -> 안익은게 있으면 -1 (영영 익지 못하는 토마토..또륵)

 

오답노트

틀린이유 너무 많음.

1. 이 문제 특이하게 열 크기를 먼저줌;;

2. 또 범위체크 안해줌 -> 이번에 문제되는 이유는 그럼 큐에 계속 들어감

3. 시간초과의 주범 : 반복문 돌때마다 토마토 다 익었는지 검사해서 반복문 빠져나가게 함, 반복문 안에 체크하는 부분 삭제하고

그냥 큐가 비었을때만 반복문 나가게 해주고 cnt-1 해서 출력하면 해결

 

소스코드

#include <iostream>
#include <queue>
using namespace std;
int n,m;
int map[1005][1005];
int visit[1005][1005];
int dr[4] = {0,0,1,-1};
int dc[4] = {1,-1,0,0};

bool isFull(){
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < m ; j++){
            if(map[i][j] == 0){
                return false;
            }
        }
    }
    return true;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> m >> n;
    queue<pair<int,int>> q;
    int input;
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < m ; j++){
            cin >> input;
            map[i][j] = input;
            if(input == 1){
                q.push(make_pair(i, j));
            }
        }
    }
    int cnt = 0;
    if(isFull()){
        cout << cnt;
        return 0;
    }
    long pushcnt = q.size();
    while(!q.empty()){
        int hereR = q.front().first;
        int hereC = q.front().second;
        q.pop();
        pushcnt--;
        visit[hereR][hereC] = true;
        for(int i = 0 ; i < 4 ; i++){
            int thereR = hereR + dr[i];
            int thereC = hereC + dc[i];
            if(thereR >= 0 && thereC >= 0 && thereR < n && thereC < m && map[thereR][thereC] == 0 && !visit[thereR][thereC]){
                q.push(make_pair(thereR,thereC));
                map[thereR][thereC] = 1;
            }
        }
        if(pushcnt == 0){
            cnt++;
            pushcnt = q.size();
        }
    }
    cout << (isFull() ? cnt-1 : -1);
    return 0;
}