백준 7569번 토마토

문제 링크입니다: https://www.acmicpc.net/problem/7569

백준 7576번 토마토(http://jaimemin.tistory.com/605)와 거의 동일하지만 2차원이 아닌 3차원이라는 점이 유일한 차이점이였습니다.

대각선에 위치할 경우 토마토는 익지 않기 때문에 6가지의 경우의 수만 고려해줍니다.(왼쪽 오른쪽 위 아래 앞 뒤)

7576번은 잠시 FIFO 개념을 혼동해서 덱(deque)을 사용했지만 이번에는 전형적인 BFS(Breadth First Search) 알고리즘답게 큐를 사용하여 풀었습니다.

#include <iostream>

#include <queue>

using namespace std;

 

const int MAX = 100;

 

typedef struct

{

        int y, x, z;

}Dir;

 

Dir moveDir[6] = { {1, 0, 0}, {-1, 0, 0}, {0, 1, 0}, {0, -1, 0}, {0, 0, 1}, {0, 0, -1} };

 

int M, N, H;

int tomato[MAX][MAX][MAX];

queue<pair<pair<int, int>, int>> q;

int noTomato;

 

//토마토가 전부 익었는지 확인

bool allRipe(void)

{

        int possible = M * N*H - noTomato;

        int cnt = 0;

 

        for (int i = 0; i < H; i++)

                 for (int j = 0; j < N; j++)

                         for (int k = 0; k < M; k++)

                                 if (tomato[j][k][i] == 1)

                                          cnt++;

 

        return possible == cnt;

}

 

int BFS(void)

{

        int day = 0;

 

        //처음부터 익힐 수 있는 토마토가 없는 경우

        if (q.empty())

                 return -1;

 

        while (!q.empty())

        {

                 int currentSize = q.size();

 

                 for (int i = 0; i < currentSize; i++)

                 {

                         int y = q.front().first.first;

                         int x = q.front().first.second;

                         int z = q.front().second;

 

                         for (int i = 0; i < 6; i++)

                         {

                                 int nextY = y + moveDir[i].y;

                                 int nextX = x + moveDir[i].x;

                                 int nextZ = z + moveDir[i].z;

 

                                 //다음 토마토가 범위 안에 있고 안 익었을 경우에만

                                 if (0 <= nextY && nextY < N && 0 <= nextX && nextX < M && 0 <= nextZ && nextZ < H)

                                          if (tomato[nextY][nextX][nextZ] == 0)

                                          {

                                                  tomato[nextY][nextX][nextZ] = 1;

                                                  q.push(make_pair(make_pair(nextY, nextX), nextZ));

                                          }

                         }

                         q.pop();

 

                         //익힐 수 있는 토마토를 전부 익혔고 전부 익었을 경우

                         if (q.size() == 0 && allRipe())

                                 return day;

                         //익힐 수 있는 토마토는 전부 익혔지만 안 익은 토마토 존재

                         else if (q.size() == 0 && !allRipe())

                                 return -1;

                 }

                 day++;

        }

}

 

int main(void)

{

        cin >> M >> N >> H;

 

        for (int i = 0; i < H; i++)

                 for (int j = 0; j < N; j++)

                         for (int k = 0; k < M; k++)

                         {

                                 cin >> tomato[j][k][i];

                                 if (tomato[j][k][i] == 1)

                                          q.push(make_pair(make_pair(j, k), i)); //익은 토마토는 큐에 넣는다

                                 if (tomato[j][k][i] == -1)

                                          noTomato++; //토마토를 넣을 수 없는 칸

                         }

 

        if (q.size() == M * N*H - noTomato)

        {

                 cout << 0 << endl; //모든 토마토 다 익었을 경우

        }

        else

        {

                 int result = BFS();

                 cout << result << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~