백준 7576번 C++ 토마토

토마토

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

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

잘 모르겠지만

이 문제를 본 건 몇 달 전인데 당시에는 DFS인지 BFS인지 아무것도 몰랐기 때문에 패스했었다.

교환학생 가기 전에 한국에서 매일 놀기도 했고...

아무튼 지금 보니 알겠다 싶어서 처음 짠 코드는

#include <iostream>
#include <stack>
using namespace std;
int box[1002][1002];
int cntZero=0, cnt;
int vi[4]={0,0,-1,1}, vj[4]={-1,1,0,0};
stack<int> si, sj;
void checkCnt(int N, int M){
    cnt=0;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++) {
            if(box[i][j]!=0)
                continue;
            for(int m=0; m<4; m++){
                if(box[i+vi[m]][j+vj[m]]==1){
                    si.push(i);
                    sj.push(j);
                    cnt++;
                    break;
                }
            }
        }
    }
}
int main(){
    int M, N;
    scanf("%d %d", &M, &N);
    for(int i=0; i<=N+1; i++){
        for(int j=0; j<=M+1; j++)
            box[i][j]=-1;
    }
    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++) {
            scanf("%d", &box[i][j]);
            if(box[i][j]==0)
                cntZero++;
        }
    }
    checkCnt(N, M);
    int day=0;
    while(cnt>0){
        while(!si.empty()&&!sj.empty()){
            box[si.top()][sj.top()]=1;
            si.pop();
            sj.pop();
        }
        cntZero-=cnt;
        checkCnt(N, M);
        day++;
    }
    if(cntZero>0){
        printf("-1");
    }else{
        printf("%d", day);
    }
    return 0;
}

였다. 어차피 초과날 걸 알고 돌렸기에 후회는 없었다. 19퍼에서 멈춘 게 조금 아쉬울 뿐...

그 다음 내가 한 것은 이 코드의 로직과는 비슷하게, 루프를 줄이는 것이었다.

이 문제를 풀 때 내가 주의했던 것은 다음과 같았다.

1. 익은 토마토는 인접한 토마토를 하루동안 익힐 수 있다.

2. 익은 토마토에 의해 익혀진 토마토를 그날 바로 체크하면 안 된다.

2번의 이유는 한번 루프를 돌 때 익은 토마토에 의해 익혀진 토마토를 익었다고 체크해버리면 그 다음 검사를 할 때 이 토마토도 포함되어 버리기 때문이다.

코드

#include <iostream>
#include <vector>
using namespace std;
int box[1002][1002];
int vi[4]={0,0,-1,1}, vj[4]={-1,1,0,0};
vector<pair<int,int>> v;
int main(){
    int M, N;
    scanf("%d %d", &M, &N);
    for(int i=0; i<=N+1; i++){
        for(int j=0; j<=M+1; j++)
            box[i][j]=-1;
    }
    int cntZero=0;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++) {
            scanf("%d", &box[i][j]);
            if(box[i][j]==1)
                v.emplace_back(i,j);
            if(box[i][j]==0)
                cntZero++;
        }
    }
    int day=0;
    vector<pair<int, int>> tmp;
    while(!v.empty()){
        for(int i=0; i<v.size(); i++){
            for(int j=0; j<4; j++){
                int ni=v[i].first+vi[j], nj=v[i].second+vj[j];
                if(box[ni][nj]==0){
                    box[ni][nj]=1;
                    tmp.emplace_back(ni, nj);
                    cntZero--;
                }
            }
        }
        if(tmp.empty())
            break;
        v.clear();
        while(!tmp.empty()){
            v.push_back(tmp.back());
            tmp.pop_back();
        }
        day++;
    }
    if(cntZero>0){
        printf("-1");
    }else{
        printf("%d", day);
    }
    return 0;
}

벡터 때문인가 메모리가 좀 많이 나온 것 같지만 제한 시간 1초 이내에 아무튼 통과!

머리가 여기까지라서 난 이것밖에 못 생각하겠다 ㅠㅠ 다른 분 코드 보면서 공부해야할 듯

한국에 돌아가기 전에는 좀 늘겠지?

emplace_back

vector<pair<int,int>> v;

를 선언하고 v.push({i,j})를 입력하니 emplace_back을 쓰라고 나왔다.

pair를 원소로 가질 때 집합 형식이 아니라 v.emplace_back(i,j)로 쓰면 깔끔하다.

자세한 설명은 geeksforgeeks 참고