백준(BOJ) 7569번 토마토

문제 : https://www.acmicpc.net/problem/7569

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.

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

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

나의 풀이:

3차원 좌표를 q에 담아서 BFS로 문제를 풀자.

 

토마토들중 익은 토마토들( 숫자 1 ) 을 모두 찾아서 큐에 넣는다. 그리고 그 갯수를 sameDay 저장한다. 즉 같은 날짜에 이 sameDay에 담긴 토마토들의 주위가 익게된다.

상하좌우 위아래(z축) 6방향으로 토마토들을 익게하면서 q에 push 해준다.

6방향으로 모두 익게 만든 sameDay에 토마토는 pop 된다.

코드 ( C++ )

#include <iostream>

#include <queue>

using namespace std;

int N, M, H;

const int MAX = 100;

int tomatoes[MAX][MAX][MAX];

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

int dy[6] = { 1,-1,0,0,0,0 };

int dx[6] = {0,0,1,-1,0,0};

// z축 방향으로 위 아래 이동

int dz[6] = { 0,0,0,0,1,-1 };

int emptyTomato;

bool TomatoCheck()

{

// 비교는 전체 토마토에서 비어있는 토마토를 뺀 수

int compare = M * N*H - emptyTomato;

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 (tomatoes[j][k][i] == 1)

cnt++;

// 익은 토마토의 개수가 비교수와 같다면 true

if (compare == cnt)

return true;

else

return false;

}

int BFS()

{

if (q.empty())

return -1;

int cnt = 0;

while (!q.empty()) {

// 같은 날짜에 퍼질 토마토들의 수를 담아준다.

int sameDay = q.size();

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

{

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

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

int z = q.front().second;

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

{

int ny = y + dy[j];

int nx = x + dx[j];

int nz = z + dz[j];

if (ny >= 0 && ny < N && nx >= 0 && nx < M && nz >= 0 && nz < H)

if (tomatoes[ny][nx][nz] == 0) {

tomatoes[ny][nx][nz] = 1;

q.push({ {ny,nx},nz });

}

}

q.pop();

 

// 큐에 담을 토마토가 없으면서 토마토를 모두 익게 만들었다면

if (q.size() == 0 && TomatoCheck() == true)

return cnt;

// 큐에 담을 토마토가 없지만 토마토가 모두 익지 않았다면

else if (q.size() == 0 && TomatoCheck() == false)

return -1;

}

cnt++;

}

}

int main()

{

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 >> tomatoes[j][k][i];

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

q.push({ {j,k},i });

// 빈 토마토들의 갯수를 센다.

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

emptyTomato++;

}

// 빈토마토들 + 처음부터 익어있었던 토마토 == 전체 토마토 수 ( 0이 없을 때 )

if ((q.size() + emptyTomato) == N * H * M)

cout << 0 << "\n";

else

{

int ans = BFS();

cout << ans << "\n";

}

return 0;

}