[백준] 7659 토마토 C++

두번째 코드가 가장 이상적인 코드

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

queue<pair<int,pair<int,int>>> q;
int m,n,h;
int arr[105][105][105],days[105][105][105];
int dn[4]={0,0,1,-1}, dm[4]={1,-1,0,0},dh[2]={1,-1};
bool flag_stop=false;

void bfs(){
    while(1){
        if(q.empty())
            break;
    
        int hh=q.front().first;
        int nn=q.front().second.first;
        int mm=q.front().second.second;
        q.pop();

        for(int i=0;i<2;i++){
            int dhh=hh+dh[i];
            if(dhh>=0 && dhh<h && arr[dhh][nn][mm]==0){
                q.push(make_pair(dhh,make_pair(nn,mm)));
                arr[dhh][nn][mm]=1;
                days[dhh][nn][mm]=days[hh][nn][mm]+1;
            }
        }
        for(int i=0;i<4;i++){
            int dmm=mm+dm[i];
            int dnn=nn+dn[i]; 
            if(dmm>=0 && dmm<m && dnn>=0 && dnn <n && arr[hh][dnn][dmm]==0){
                q.push(make_pair(hh,make_pair(dnn,dmm)));
                arr[hh][dnn][dmm]=1;
                days[hh][dnn][dmm]=days[hh][nn][mm]+1;
            }  
        }
    }

void print(){
    int max_days=-1;
    //안 익은 토마토가 있는지 확인
    for(int j=0;j<h;j++){
        for(int i=0;i<n;i++){
            for(int k=0;k<m;k++){
                max_days=max(max_days,days[j][i][k]);
                if(arr[j][i][k]==0){ 
                    max_days=-1;
                    flag_stop=true;
                    break;
                }
            }
            if(flag_stop)
                break;
        }
        if (flag_stop)
            break;
    }
    //소요 날짜 출력
    cout << max_days <<endl;
}
int main() {  
    cin >> m >> n >> h;
    for(int j=0;j<h;j++){
        for(int i=0;i<n;i++){
            for(int k=0;k<m;k++){
                cin >> arr[j][i][k];
                if(arr[j][i][k]==1){
                    q.push(make_pair(j,make_pair(i,k)));
                    days[j][i][k]=0;
                }
            }
        }
    }

    bfs();
    print();
    
    return 0;
}

 

개선점1) dh dn dm 을 6차원으로 변경

개선점2) 날짜를 저장하는 days 배열 추가 (dist 거리 배열)

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
queue<pair<int,pair<int,int>>> q;
int m,n,h;
int arr[105][105][105],days[105][105][105];
int dn[6]={0,0,1,-1,0,0}, dm[6]={1,-1,0,0,0,0},dh[6]={0,0,0,0,1,-1};
bool flag_stop=false;

void bfs(){
    while(1){
        if(q.empty())
            break;
    
        int hh=q.front().first;
        int nn=q.front().second.first;
        int mm=q.front().second.second;
        q.pop();

        for(int i=0;i<6;i++){
            int dhh=hh+dh[i];
            int dmm=mm+dm[i];
            int dnn=nn+dn[i]; 
            if(dmm>=0 && dmm<m && dnn>=0 && dnn <n && dhh>=0 && dhh <h && arr[dhh][dnn][dmm]==0){
                q.push(make_pair(dhh,make_pair(dnn,dmm)));
                arr[dhh][dnn][dmm]=1;
                days[dhh][dnn][dmm]=days[hh][nn][mm]+1;
            }
            
        }
        
    }
}
void print(){
    int max_days=-1;
    
    for(int j=0;j<h;j++){
        for(int i=0;i<n;i++){
            for(int k=0;k<m;k++){
                max_days=max(max_days,days[j][i][k]);
                if(days[j][i][k]==-1){ 
                    cout << -1 ;
                    return ;
                }
            }
        }
    }
    cout << max_days <<endl;
}

int main() {
    cin >> m >> n >> h;
    for(int j=0;j<h;j++){
        for(int i=0;i<n;i++){
            for(int k=0;k<m;k++){
                cin >> arr[j][i][k];
                if(arr[j][i][k]==1){
                    q.push(make_pair(j,make_pair(i,k)));
                    days[j][i][k]=0;
                }
                else if(arr[j][i][k]==0)
                    days[j][i][k]=-1;  
            }
        }
    }

  
    bfs();
    print();
    
    return 0;
}

이 문제에서는 특정 위치에 빠르게 접근해야 되고 범위가 정해져 있기 때문에 배열을 사용하는 것이 좋다.

 

3차원 요소를 저장할 queue 선언 방법은 queue<pair<a<pair<b,c>>> q