https://www.acmicpc.net/problem/7569
문제
> 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다.
> 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.
> 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다.
> 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다.
> 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다.
> 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다.
> 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.
> 토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때,
며칠이 지나면 토마토들이 모두 익는지,
그 최소 일수를 구하는 프로그램을 작성하라.
> 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.
접근
3차원벡터를 사용해 토마토의 좌표를 저장하면서 안익은토마토가 있는지 본다. 없다면 바로 0을 출력하고 끝내고 있다면 익은 토마토들의 좌표만 따로 잡아 큐에 넣어둔다.
while문으로 돌며 큐에 있는 토마토의 개수를 기준으로 for문을 돌며 큐에 영향을 받은 토마토들의 좌표를 넣는다.
이 과정이 끝나면 하루가 지났다 라는 뜻으로 하고 cnt를 누적하며 다시 while문을 돈다. 만약 큐에 들어가는 토마토가 없으면 깨고 나와 모든 토마토를 한번 돈다. 0인 익지않은 토마토가 있으면 -1을 출력하고 없으면 cnt, 모두 익는데 걸린 날을 출력한다.
문제해결
> 토마토의 x좌표인 m, y좌표인 n, z좌표인 h를 입력받고 토마토의 상태를 저장할 tomato3차원 벡터, 방문처리를 통해 영향에 대해 처리할 visited벡터를 선언한다.
> 3차원을 다루기 위해 구조체로 x,y,z를 정의해준다.
> 이제 토마토를 입력받으면서 1또는 -1밖에 없으면 ripe값이 true로 0을 출력하고 끝내주고 아니면 false로 아래로 넘어간다.
> 큐를 하나만들고 거기에 익은 토마토들의 초기 좌표만 잡아서 넣어주고 중복방지를 위해 방문처리를 해준다.
> 큐의 크기만큼 반복문을 돌며 각 일차 별로의 토마토 영향변화를 따져준다. 6방향 탐색을 하며 영향 받을 토마토를 골라주고 큐에 넣어준다.
> 해당 for문이 끝나면 하루가 지났으므로 cnt를 누적하고 큐에 영향 받은 토마토가 있나없나 본뒤 없으면 while문을 깨고, 있다면 다시 영향을 끼친다.
> 위 과정이 끝난뒤 모든 토마토가 영향을 받았나 보기위해 전체 토마토드를 한번 돈다. 하나라도 0이 있다면 영향을 못받는 애가 있으므로 -1을 출력하고 없다면 걸린 날인 cnt를 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int M, N, H;
vector<vector<vector<int>>> tomato;
vector<vector<vector<bool>>> visited;
int dix[6] = { 0, 0, -1, 1, 0, 0 };
int diy[6] = { 0, 0, 0, 0, 1, -1 };
int diz[6] = { 1, -1, 0, 0, 0, 0 };
struct pos
{
int x;
int y;
int z;
};
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> M >> N >> H;
tomato.resize(H, vector<vector<int>>(N, vector<int>(M)));
visited.assign(H, vector<vector<bool>>(N, vector<bool>(M, false)));
bool ripe = true;
for (int h = 0; h < H; h++)
{
for (int n = 0; n < N; n++)
{
for (int m = 0; m < M; m++)
{
int t;
cin >> t;
tomato[h][n][m] = t;
if (t != 0) continue; //하나라도 안익은게 있는지
ripe = false; //익혀야 하는 애가 있다.
}
}
}
if (ripe) //안익은게 하나도 없으면
{
cout << 0 << '\n';
return 0;
}
queue<pos> q;
for (int h = 0; h < H; h++)
{
for (int n = 0; n < N; n++)
{
for (int m = 0; m < M; m++)
{
if (tomato[h][n][m] != 1) continue;
if (visited[h][n][m]) continue;
q.push({ m, n, h });
visited[h][n][m] = true;
}
}
}
int cnt = 0;
while (1)
{
int t = q.size();
for (int i = 0; i < t; i++)
{
int fx = q.front().x;
int fy = q.front().y;
int fz = q.front().z;
q.pop();
for (int i = 0; i < 6; i++)
{
int nx = fx + dix[i];
int ny = fy + diy[i];
int nz = fz + diz[i];
if (nx < 0 || nx >= M) continue;
if (ny < 0 || ny >= N) continue;
if (nz < 0 || nz >= H) continue;
if (tomato[nz][ny][nx] != 0) continue;
if (!visited[nz][ny][nx])
{
tomato[nz][ny][nx] = 1;
q.push({ nx, ny, nz });
visited[nz][ny][nx] = true;
}
}
}
if (q.empty()) break;
cnt += 1;
}
for (int h = 0; h < H; h++)
{
for (int n = 0; n < N; n++)
{
for (int m = 0; m < M; m++)
{
if (tomato[h][n][m] == 0)
{
cout << -1 << '\n';
return 0;
}
}
}
}
cout << cnt << '\n';
}
후기
가장 복잡했던건 날짜의 처리였다. 기존 처럼 BFS로 했는데 한 토마토로 가능한 모든 토마토가 영향을 받게 되므로 날짜를 자르기 애매했다.
그래서 각각 큐에 들어온 애들의 개수를 세서 그 거만큼만 돌리면 날짜를 뜻하게 되니까 그렇게 헀는데 맞았다.
