[백준] 7569번 토마토 (C++)

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

문제 설명

h개의 n X m의 배열이 주어졌을 때, 토마토가 며칠이 지나면 다 익게 되는지 최소 일수를 구하는 문제이다.

익은 토마토는 하루가 지나면 위, 아래, 왼쪽, 오른쪽, 앞, 뒤에 있는 토마토에 영향을 주어 그 토마토를 익게 한다. 

 

주요 로직

1. 최소 일수를 구하는 문제이기에 bfs로 풀어야 한다.

 

정답 코드

#include <bits/stdc++.h>

using namespace std;

struct A{
	int a,b,c;
};
int n,m,h;
vector<A> v;
int arr[104][104][104], visited[104][104][104];
int dx[6] = {0,0,1,0,0,-1}, dy[6] = {0,1,0,0,-1,0}, dz[6] = {-1,0,0,1,0,0};

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> n >> m >> h;
	for(int i=0; i<h; i++){
		for(int j=0; j<m; j++){
			for(int k=0; k<n; k++){
				cin >> arr[i][j][k];
				if(arr[i][j][k] == 1) v.push_back({i,j,k});
			}
		}
	}
	
	queue<A> q;
	for(auto it : v){
		visited[it.a][it.b][it.c] = 1;
		q.push({it.a, it.b, it.c});
	}
	
	while(q.size()){
		int z = q.front().a;
		int y = q.front().b;
		int x = q.front().c;
		q.pop();
		for(int i=0; i<6; i++){
			int nz = z + dz[i];
			int ny = y + dy[i];
			int nx = x + dx[i];
			if(nz < 0 || ny < 0 || nx < 0 || nz >= h || ny >= m || nx >= n) continue;
			if(visited[nz][ny][nx]) continue;
			if(arr[nz][ny][nx] == -1 || arr[nz][ny][nx] == 1) continue;
			visited[nz][ny][nx] = visited[z][y][x] + 1;
			q.push({nz,ny,nx});
		}
	}
	
	int ret = 0;
	bool flag = true;
	for(int i=0; i<h; i++){
		for(int j=0; j<m; j++){
			for(int k=0; k<n; k++){
				if(visited[i][j][k]) ret = max(ret, visited[i][j][k]);
				if(!visited[i][j][k] && arr[i][j][k] != -1) flag = false;
			}
		}
	}
	
	if(flag) cout << ret-1 << "\n";
	else cout << "-1\n";
	
	return 0;
}