백준 7569 - 토마토

문제 링크 입니다. https://www.acmicpc.net/problem/7569

7569번: 토마토

3차원 BFS를 요구하는 문제입니다. 3차원 배열을 선언할때 Z축을 맨 앞에, X,Y축 순서로 만들어야합니다.

예를 들면 tomato[z][x][y]입니다. 자세한 것은 코드를 참고해주세요!

3차원 BFS를 해야하기 때문에 기존의 4방향과는 다르게 6방향으로 탐색을 해줘야합니다.

처음 입력을 받을때 익지 않은 토마토의 갯수를 셉니다.

익지 않은 토마토의 갯수가 0이라면 바로 0을 출력하고 0이 아니라면 BFS를 실행했습니다.

최소 일수를 구하기 위해서 max_day라는 변수를 하나 만들어주고 check배열의 값과 계속 비교해 큰 값을 집어 넣습니다. check배열은 토마토가 익은 날짜가 몇일인지를 저장하는 배열이기에 check배열과 계속해서 비교했습니다.

BFS가 실행될 때마다 토마토의 갯수를 하나씩 줄이고 BFS가 끝났을 때 남은 토마토의 갯수가 0이라면 날짜를 출력했습니다.

자세한 것은 코드를 보고 참고해주세요

 

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>

using namespace std;
int tomato[101][101][101];
int check[101][101][101];
int number_tomato;
typedef struct qu {
	int x;
	int y;
	int z;
}qu;
queue<qu> q;
int arr[6]  = { 1,0,-1,0,0,0 };
int arr2[6] = { 0,-1,0,1,0,0 };
int arr3[6] = { 0,0,0,0,1,-1 };
int M, N, H;
int max_day;

void bfs() {
	while (!q.empty()) {
		int x1 = q.front().x;
		int y1 = q.front().y;
		int z1 = q.front().z;
		q.pop();
		for (int i = 0; i < 6; i++) {
			int xx = x1 + arr[i];
			int yy = y1 + arr2[i];
			int zz = z1 + arr3[i];
			if (xx >= 1 && xx <= N && yy >= 1 && yy <= M && zz >= 1 && zz <= H) {
				if (check[zz][xx][yy] == 0 && tomato[zz][xx][yy] == 0) {
					tomato[zz][xx][yy] = 1;
					check[zz][xx][yy] = check[z1][x1][y1] + 1;
					number_tomato--;
					max_day = max(max_day, check[zz][xx][yy]);
					q.push({ xx,yy,zz });
				}
			}
		}
	}
	if (number_tomato == 0) {
		cout << max_day - 1;
	}
	else {
		cout << "-1";
	}
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> M >> N >> H;
	for (int k = 1; k <= H; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				cin >> tomato[k][i][j];
				if (tomato[k][i][j] == 0) {
					number_tomato++;
				}
				if (tomato[k][i][j] == 1) {
					check[k][i][j] = 1;
					q.push({ i,j,k });
				}
			}
		}
	}
	if (number_tomato == 0) {
		cout << "0";
	}
	else bfs();
	return 0;
}

 

질문, 조언 있다면 댓글 남겨주세요