백준(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;
}
