문제 URL
https://www.acmicpc.net/problem/7569
7569번: 토마토
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100,
www.acmicpc.net
[문제 설명]
다음 문제는 아래와 같은 주어진 조건이 있을 때 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 문제이다.
[문제 풀이]
1. 삼차원 배열 입력받기, 값이 1인 위치는 큐에 따로 저장
2. BFS를 통해 익은 토마토와 인접한 토마토의 값을 1로 변경하기
3. 익지 않은 토마토(값이 0)가 있는지 확인하고 결과 출력하기
#include <iostream>
#include <queue>
using namespace std;
int graph[100][100][100];
// 행, 열, 세로
int dir[6][3]{ {1,0,0},{0,1,0},{-1,0,0},{0,-1,0},{0,0,1},{0,0,-1} };
int R, C, H;
queue<pair<pair<int, int>, int>> q;
void bfs() {
int cnt = 0;
while (!q.empty()) {
int size = q.size();
cnt++;
for (int i = 0; i < size; i++) {
int r = q.front().first.first;
int c = q.front().first.second;
int h = q.front().second;
q.pop();
for (int j = 0; j < 6; j++) {
int nr = r + dir[j][0];
int nc = c + dir[j][1];
int nh = h + dir[j][2];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && nh >= 0 && nh < H && graph[nh][nr][nc] == 0) {
q.push({ {nr,nc} ,nh });
graph[nh][nr][nc] = 1;
}
}
}
}
// 익지 않은 토마토가 있는지 확인
for (int i = 0; i < H; i++) {
for (int j = 0; j < R; j++) {
for (int k = 0; k < C; k++) {
if (graph[i][j][k] == 0) {
cout << -1;
return;
}
}
}
}
// 가능한 모든 토마토가 익었을 때도, while문이 한 번 더 돌기 때문에 -1을 해줌
cout << cnt-1;
}
int main() {
cin >> C >> R >> H;
for (int i = 0; i < H; i++) {
for (int j = 0; j < R; j++) {
for (int k = 0; k < C; k++) {
cin >> graph[i][j][k];
if (graph[i][j][k] == 1) {
q.push({ {j,k},i });
}
}
}
}
bfs();
}