[백준 7569번 / C++] 토마토

[백준 6593번 / C++ ] 상범 빌딩

---

위의 문제와 상당히 비슷한 BFS문제이다. 

 

#접근방법

 

토마토 문제는 상하좌우만 고려할 것이 아니라 윗층과 아랫층을 검사해야한다. 

즉, queue에다가 y와 x 그리고 layer까지 고려한 데이터 값을 함께 넣어준다. 

 

그리고 map이 가로와 세로를 넘어갔을 때만 체크해주는 것이 아니라 layer의 높이까지 고려해야한다. 

 

익지 않은 tomato 개수를 미리 저장을 해주고 bfs를 호출해서 현재 익은 토마토에서 주변에 안익은 토마토가 있다면 익지 않은 tomato 개수를 줄여주고 queue에다가 익지 않은 토마토의 좌표값과 layer 값을 넣어준다.

 

해당 좌표값의 map을 1로 세팅해주면서 익었다는 표시를 해준다. 

 

결과값은 익지 않은 tomato 개수가 0이 되지 않았다면 "-1" 출력.   0이라면 time 값 출력  

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std; 
int tomato; 
int m, n, layer; 
int dx[4] = { 0,0,1,-1 }; 
int dy[4] = { 1,-1,0,0 }; 
int map[100][100][100]; 
int visited[100][100][100]; 
int dist[100][100][100]; 
int time; 
queue <pair<pair<int, int>, int>>q; 
void bfs() {
	
	while (!q.empty()) {
		int y, x, lay;
		int sz= q.size(); 
		
		while (sz--) {
			
			y = q.front().first.first;
			x = q.front().first.second;
			lay = q.front().second;
		
			q.pop(); 

			for (int i = 0; i < 6; i++) {
				int nx = x;
				int ny = y;
				int l = lay;
				if (i == 4) l += 1;
				else if (i == 5) l -= 1;
				else {
					nx += dx[i];
					ny += dy[i];
				}
				if (l < 0 || l >= layer || ny < 0 || ny >= m || nx < 0 || nx >= n)continue;
				if (map[l][ny][nx] == -1||map[l][ny][nx]|| visited[l][ny][nx])continue;
			
				map[l][ny][nx] = 1; 
				dist[l][ny][nx] = dist[lay][y][x] + 1; 
				time = dist[l][ny][nx]; 
				tomato--;
				visited[l][ny][nx] = 1; 
				q.push(make_pair(make_pair(ny, nx), l));
			}
		}
		
	}
}


int main() {
	cin >> n >> m >> layer; 
	for (int i = 0; i < layer; i++) {
		for (int j = 0; j < m; j++) {
			for (int k = 0; k < n; k++) {
				cin >> map[i][j][k]; 
				if (map[i][j][k] == 1) {
					visited[i][j][k] = 1; 
					q.push(make_pair(make_pair(j, k), i)); 
				}
				if (map[i][j][k] == 0)tomato++; 
			}
		}
	}
	bfs(); 	
	if (tomato)cout << -1;
	else cout<<time; 
	return 0; 


}

7569번: 토마토