백준 7569_토마토 3D 문제풀이 in C++
문제 URL
https://www.acmicpc.net/problem/7569
문제 요구사항
- 하루에 한 칸씩 익은 토마토들의 영향이 전이되어 익지 않은 토마토들이 익게 된다.
- 이때, 모든 토마토가 익게 되는 최소한의 시간을 구하여라.
- 첫번째 줄에는 토마토 상자 크기가 주어진다. (M, N, H)
- 이어서 토마토 맵의 값이 주어진다.
- -1은 토마토가 안 들어있는 칸
- 0은 익지 않은 토마토가 들어있는 칸
- 1은 익은 토마토가 들어있는 칸
특이사항
- 이전 문제인 토마토에서 같은 풀이 방법으로 접근하되 상자가 층으로 쌓인(3D) 문제이다.
접근 방법
- ‘여러 군데에 익은 토마토가 있을 시 어떻게 접근해야 하는가?’를 해결하면 이 문제를 풀 수 있게 된다. 해당 문제는 칸 입력 시 1일 때, 그 좌표 값을 큐에 넣어 BFS 반복 좌표를 해당 좌표로 선정한다. 또, 미로 탐색(최소 이동)과 비슷하게 풀이하면 되는데 해당 문제는 이동 할 수 있는(덜 익은 토마토가 있는) 모든 칸을 이동하는데 걸리는 시간을 구하면 된다. 즉, 모든 칸을 가면 되기 때문에 Check를 굳이 할 필요가 없다.
풀이 순서
- 토마토 맵 입력 시 1인 경우(익은 토마토인 경우) 해당 좌표를 큐에 넣는다.
- BFS 함수 작성 시 다음 칸이 이동 가능하면 현재 자리 값에 + 1 한 값을 다음 칸에 대입한다.
- 이렇게 만들어진 토마토 맵을 다시 반복문을 이용해서 탐색한다. 이때, 0이 하나라도 존재하면 -1을 출력하고 프로그램 종료, 아니라면 result 값과 맵의 각 값을 비교하며 최대로 큰 값을 대입한다.
기존 풀이에서 추가된 사항
- 3차원이므로 dx, dy, dh 배열이 필요하며 각각 6개의 원소를 갖는다. (순서는 동, 남, 서, 북, 위, 아래 순으로 했다)
- pair를 두 번 써서 3개의 좌표를 갖는 큐를 만들어도 됐는데 구조가 복잡해질 것 같아 그냥 구조체를 하나 만들었다.
- BFS 수행 전 맵에 0이 없으면 (덜 익은 토마토가 없음) 0 출력하고 프로그램 종료
- 배열 접근 변수를 잘못 써주는 바람에 자꾸 오류가 났다… [차원][행][열] 이 순인데, BFS에서 [행][열][차원] 순으로 값을 대입했더니 엉뚱한 답이 나오고, 결과 출력에서 원치 않은 답이 나왔다….
소스코드
#include <iostream>
#include <queue>
using namespace std;
struct dimension {
int D;
int R;
int C;
};
queue<dimension> q3D;
int tomato3DMap[100][100][100];
// 동, 남, 서, 북, 위, 아래
int dx3D[] = { 1, 0, -1, 0, 0, 0 };
int dy3D[] = { 0, 1, 0, -1, 0, 0 };
int dh3D[] = { 0, 0, 0, 0, 1, -1 };
int result = 0;
int D, R, C;
void tomato3DBFS() {
while (!q3D.empty()) {
int xx = q3D.front().R;
int yy = q3D.front().C;
int hh = q3D.front().D;
q3D.pop();
for (int i = 0; i < 6; i++) {
int nx = xx + dx3D[i];
int ny = yy + dy3D[i];
int nh = hh + dh3D[i];
if (nx >= 0 && ny >= 0 && nh >= 0 && nx < R && ny < C && nh < D) {
if (tomato3DMap[nh][nx][ny] == 0) {
tomato3DMap[nh][nx][ny] = tomato3DMap[hh][xx][yy] + 1;
q3D.push({ nh, nx, ny });
}
}
}
}
}
void tomato3D() {
int flag = 1;
cin >> C >> R >> D;
for (int i = 0; i < D; i++) {
for (int j = 0; j < R; j++) {
for (int k = 0; k < C; k++) {
cin >> tomato3DMap[i][j][k];
if (tomato3DMap[i][j][k] == 1) {
q3D.push({ i, j, k });
}
}
}
}
for (int i = 0; i < D; i++) {
for (int j = 0; j < R; j++) {
for (int k = 0; k < C; k++) {
if (tomato3DMap[i][j][k] == 0) {
flag = 0;
break;
}
}
if (!flag)
break;
}
if (!flag)
break;
}
if (flag) {
cout << 0 << "\n";
}
else {
tomato3DBFS();
for (int i = 0; i < D; i++) {
for (int j = 0; j < R; j++) {
for (int k = 0; k < C; k++) {
if (tomato3DMap[i][j][k] == 0) {
cout << -1 << "\n";
return;
}
if (result < tomato3DMap[i][j][k]) {
result = tomato3DMap[i][j][k];
}
}
}
}
cout << result -1 << "\n";
}
}
int main() {
tomato3D();
return 0;
}
문제 풀이 결과
