[백준] #7509 토마토🍅

• 백준 # 7509 토마토
• 사용 언어 : C++
• 난이도 : 골드Ⅴ🥇

문제

• 예제 입력
  

창고에 토마토가 저장되어있다. 창고의 각 자리에는 익은 토마토가 있거나, 익지 않은 토마토가 있거나, 토마토가 없다.

익은 토마토는 다음 날에 주변(상,하,좌,우,위,아래) 토마토를 익게 한다.

전체 토마토를 익게 만들려면 몇일이 필요한지 구하여 출력하시오.

만약 이미 토마토가 모두 익어있다면 0을 출력하고, 전체 토마토를 익힐 수 없다면 -1 을 출력해라.

분석

익은 토마토의 주변에 있는 토마토만 익을 수 있다.
즉, 현재 익을 수 있는 토마토는, 익은 토마토 주변에 있는 안익은 토마토이다.

다시 말하면, 익은 토마토의 주변(상,하,좌,우,위,아래) 만 검사하여 토마토가 있는지 확인하면 된다.

⇒ BFS 사용

이때, 주어진 문제가 ‘다 익을 때까지 걸린 날짜’ 를 구하는 것이므로, BFS 탐색의 깊이(depth)를 한 단계씩 늘려나갈 수 있는 지표가 필요하다.

⇒ 주변 칸을 탐색하기 직전의 queue의 크기

마지막으로 bfs가 종료되었을 때, 지금까지 익힌 토마토 개수 < 전체 토마토 개수이면 익힐 수 없는 토마토가 존재한다는 뜻이므로 -1 출력하고, 지금까지 익힌 토마토 개수 == 전체 토마토 개수 라면 모든 토마토를 익혔다는 것이므로 걸린 날짜를 출력한다.

코드

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

int M,N,H; // 토마토 박스 크기 
int i,j,k; // 반복문
int day=0; // 걸린날짜 
int cnt=0; // 전체 토마토 개수 
int cur=0; // 현재 익은 토마토 개수 

vector<vector<vector<int>>> tomatoes; // 토마토담는 3차원 배열 

// queue에 저장할 구조체 (x,y,z좌표)
struct T{
    int x;
    int y;
    int z;
};

vector<int> dx = {0,0,-1,1,0,0};// 상하좌우위아래
vector<int> dy = {1,-1,0,0,0,0};// 상하좌우위아래
vector<int> dz = {0,0,0,0,1,-1};// 상하좌우위아래

queue<T> bfsQ;

void bfs(){
    int p,q;
    while(cur <cnt && !bfsQ.empty()){ // 종료조건 cur == cnt 또는 bfsQ.empty
        int size = bfsQ.size(); // 이 개수만큼만 pop, 나머지는 자식노드이므로 다음 loop에서 pop
        
        for(p=0;p<size;p++){
            T t=bfsQ.front();
            bfsQ.pop();
            if(tomatoes[t.z][t.y][t.x]==1) 
                continue;
            
            // 마킹     
            tomatoes[t.z][t.y][t.x]=1;
            cur++;
            
            // 상하 좌우 위아래 탐색 
            for(q=0;q<6;q++){
                if(t.x+dx[q]<0 ||t.x+dx[q]>=M ||t.y+dy[q]<0 ||t.y+dy[q]>=N||t.z+dz[q]<0 ||t.z+dz[q]>=H)
                    continue;
                    
                int curX = t.x+dx[q];
                int curY = t.y+dy[q];
                int curZ = t.z+dz[q];
                
                if (tomatoes[curZ][curY][curX]==0){
                    T child={curX,curY,curZ};
                    bfsQ.push(child);
                }
            }
        }
        day++;
        
    }
    
}

int main()
{
    cin>> M>>N>>H;
   
    for(i=0;i<H;i++){
        tomatoes.push_back(vector<vector<int>>(N,vector<int>(M,0)));
    }
    
    for(i=0;i<H;i++){
        for(j=0;j<N;j++){
            for(k=0;k<M;k++){
                int state;
                cin >> state;
                
                if(state==1){ // bfs에서 1로 마킹할 것이므로 일단 push 만 
                    T tomato ={k,j,i};
                    bfsQ.push(tomato);
                    cnt++; // 전체 토마토 개수 cnt
                }else if(state==0)
                    cnt++; // 전체 토마토 개수 cnt
                else
                    tomatoes[i][j][k]=state;
            }
        }
    }
    
    bfs();
    
    if(cur<cnt)
        cout<< -1;
    else
        cout <<day -1;
    return 0;
}

느낀 점

이번 문제의 첫 시도에서 BFS의 depth를 구분하는 방법을 몰라, queue를 여러개 사용했었다. 그랬더니 메모리 초과가 발생하였다. (이전에 비슷한 문제를 풀었을 때도 queue 여러개 사용했었는데, 낮은 난이도의 문제라 메모리를 넉넉하게 주었던 것같다..)

검색을 통해, bfs에서 각 loop 진행 전 queue의 사이즈로 depth를 구분할 수 있다는 사실을 알게 되었고, 덕분에 문제를 해결할 수 있었다.

이제라도 효율적인 방법을 찾아서 다행이다...! 다음에는 이런 실수 말아야지