백준 7569번 토마토 C++

BFS로 풀었다.

 

#include <iostream>
#include <queue>
using namespace std;

int arr[101][101][101]{};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int m, n, h;
	cin >> m >> n >> h;

	queue<pair<int, pair<int, int>>> q;
	int zeroTomato = 0;
	
	for (int i = 0; i < h; ++i) 
		for (int j = 0; j < n; ++j) 
			for (int k = 0; k < m; ++k) {
				cin >> arr[i][j][k];

				if (arr[i][j][k] == 1) 
					q.push({ i,{j, k} });
				else if (arr[i][j][k] == 0)
					++zeroTomato;
			}

	int dz[6] = { 0, 0, 0, 0, 1, -1 };
	int dy[6] = { 1, -1, 0, 0, 0, 0 };
	int dx[6] = { 0, 0, -1, 1, 0, 0 };
	
	int result = 0;
	int oneDaySize = q.size();
	
	while (!q.empty()) {
		int height = q.front().first;
		int y = q.front().second.first;
		int x = q.front().second.second;

		q.pop();
		
		for (int i = 0; i < 6; ++i) {
			int nz = height + dz[i];
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (nz < 0 || nz >= h || ny < 0 || ny >= n || nx < 0 || nx >= m)
				continue;

			if (arr[nz][ny][nx] == 0) {
				q.push({ nz, {ny, nx} });
				arr[nz][ny][nx] = 1;

				--zeroTomato;
			}
		}
        
		--oneDaySize;

		if (oneDaySize == 0 && !q.empty()) {
			++result;
			oneDaySize = q.size();
		}
	}

	if (zeroTomato == 0)
		cout << result;
	else
		cout << "-1";

	return 0;
}

 

다른 문제를 풀 때 사용했던 2차원 배열에서 3차원으로 확장 시켰다.

 

zeroTomato라는 변수를 선언해, 입력을 받을 당시 익지 않은 토마토가 몇개인지 세었고

queue에 토마토가 들어올 때 하나씩 빼주어

while문을 빠졌나왔을때, 이 zeroTomato가 0이면 모든 토마토가 익었다는 의미이므로

zeroTomato가 0이면 result 출력, 0이 아니면 -1을 출력하도록 했다.

 

oneDaySize는 입력을 다 받은 후의 queue 사이즈가

하루동안 while문이 돌아가는 횟수이므로,

0이 된다면 ++result, oneDaySize를 다시 queue의 사이즈로 채워넣는 것을 반복한다.

 

 

https://www.acmicpc.net/problem/7569