[백준] 7569 - 토마토 (C++)

문제 출처 :

www.acmicpc.net/problem/7569

7569번: 토마토

문제 풀이 :

• 지난번에 푼 토마토 문제(문제번호를 보면 다른 문제다 !)와 매우 흡사한 문제다. 다른점은 그냥 3차원으로 확장했다는 것인데 사실 3차원으로 확장한다해도 결국은 컴퓨터에겐 3차원의 개념이 없다는 점에서 index만 잘 고려해 준다면 크게 어려울 것이 없다.
• 지난번 토마토 문제에서와 바뀐점은 그냥 h(높이 부분)에 해당되는 움직임만 추가해주고 전체 로직은 똑같다.
• 다만 C++로 문제를 풀 경우 Python과 다르게 자료구조를 어떻게 쓸 것인가에 대한 고민이 조금 시간이 걸렸다.
• Python으로 풀 땐 tuple 형식으로 unpacking 하면서 직관적으로 사용이 가능했지만 C++의 경우는 pair을 두개를 써서 이부분을 해결했다.
• 또한 C++에서 deque 자료구조는 pop_back 할 경우 return 값이 없다( python과 다르다). 때문에 index를 통해서 먼저 참조하고, 그후 맨 뒷 값을 없애주는 방식으로 구성했다.

C++

#include <iostream>
#include <algorithm>
#include <deque>
#include <utility>


using namespace std;

int m;
int n;
int h;

int bfs(int farm[101][101][101],deque<pair<pair<int,int>,int>> tomatos,int cnt,int ny_tomato)
{
    bool condition = true;
    int dx[] = {-1,0,0,1,0,0};
    int dy[] ={0,-1,0,0,1,0};
    int dh[] = {0,0,-1,0,0,1};


    int tomato_x =0;
    int tomato_y = 0;
    int tomato_h =0;

    while(condition)
    {
        deque<pair<pair<int,int>,int>> next_tomatos ={};
        condition = false;
        cnt +=1;
        while(!tomatos.empty())
        {
            int idx = tomatos.size();
            pair<pair<int,int>,int> tomato;
            tomato = tomatos[idx-1];
            tomatos.pop_back();
            tomato_x = tomato.first.first;
            tomato_y = tomato.first.second;
            tomato_h = tomato.second;

            for(int i=0;i<6;i++)
            {
                int nx = tomato_x + dx[i];
                int ny = tomato_y + dy[i];
                int nh = tomato_h + dh[i];
                if(nx>=0 && ny>=0 && nh>=0 && nx<m && ny<n && nh<h)
                {
                    int value = farm[nh][ny][nx];
                    if(value==0)
                    {
                        ny_tomato -=1;
                        pair<int,int> temp1 (nx,ny);
                        pair<pair<int,int>,int> temp(temp1,nh);
                        next_tomatos.push_back(temp);
                        if(ny_tomato==0)
                        {
                            return cnt;
                        }
                        farm[nh][ny][nx]=1;
                    }
                }
            }
            condition = true;
        }
        tomatos=next_tomatos;
    }
    return -1;
}

int main()
{
    cin >>m>>n>>h;
    int farm[101][101][101]={0,};

    for(int h_ =0;h_<h;h_++)
    {
        for(int i=0;i<n;i++ ) {
            for (int j = 0; j < m; j++)
            {
                int temp_ = 0;
                cin>>temp_;
                farm[h_][i][j]=temp_;
            }
        }
    }
    int ny_tomato=0;
    deque<pair<pair<int,int>,int>> tomatos;
    int no_tomato =0;
    int cnt=0;
    int t_cnt = 0;
    for(int k=0;k<h;k++)
    {
        for(int i=0;i<n;i++)
        {
            for (int j=0;j<m;j++)
            {
                if(farm[k][i][j]==1)
                {
                    t_cnt +=1;
                    pair<int,int> temp1 (j,i);
                    pair<pair<int,int>,int> temp(temp1,k);
                    tomatos.push_back(temp);
                }
                else if(farm[k][i][j]==0)
                {
                    ny_tomato+=1;
                }
                else
                {
                    no_tomato+=1;
                }
            }
        }
    }
    if(t_cnt==0)
    {
        cout << -1;
    }
    else if(t_cnt + no_tomato ==(m*n*h))
    {
        cout << 0;
    }
    else
    {
        cout << bfs(farm,tomatos,cnt,ny_tomato);
    }
    return 0;
}

Python

#import  numpy as np


def bfs(farm, tomatos, cnt, ny_tomato):
    condition = True
    global m,n,h
    dx = [-1, 0, 0, 1,0,0]
    dy = [0, -1, 0, 0,1,0]
    dh = [0, 0, -1, 0,0,1]
    while (condition):
        next_tomato = []
        condition = False
        cnt += 1
        while (tomatos):
            tomato = tomatos.pop()
            h_,y, x = tomato
            for i in range(6):
                temp_x = x + dx[i]
                temp_y = y + dy[i]
                temp_h = h_ + dh[i]
                if (temp_x >= 0 and temp_y >= 0 and temp_x < m and temp_y < n and temp_h >=0 and temp_h <h):
                    value = farm[temp_h][temp_y][temp_x]
                    if value == 0:
                        ny_tomato -= 1
                        next_tomato.append((temp_h,temp_y, temp_x))
                        if (ny_tomato == 0):
                            return cnt
                        farm[temp_h][temp_y][temp_x] = 1
            condition=True
        tomatos = next_tomato
    return -1


if __name__ == "__main__":
    m,n ,h= map(int,input().split())
    farm = [[list(map(int,input().split())) for _ in range(n)] for _ in range(h)]
    #print(np.array(farm))
    ny_tomato = 0
    tomato_loc = []
    no_tomato = 0
    cnt =0
    tomato_cnt = 0
    for k in range(h):
        for i in range(n):
            for j in range(m):
                if(farm[k][i][j]==1):
                    tomato_cnt+=1
                    tomato_loc.append((k,i,j))
                elif(farm[k][i][j]==0):
                    ny_tomato +=1

                elif(farm[k][i][j]==-1):
                    no_tomato+=1

    if(tomato_cnt ==0):
        print(-1)
    elif(tomato_cnt + no_tomato == (m*n*h)):
        print(0)
    else:
        print(bfs(farm,tomato_loc,cnt,ny_tomato))