백준 7569 토마토

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

7569번: 토마토

 

- 그래프 탐색 문제인데, 특이하게도 3차원으로 값이 주어져서 난이도가 조금 올라가는 문제이다. 따라서, 필자는 3차원 배열을 활용하였고 M,N,H를 각각 X,Y,Z로 두어서 계산을 하였다.(각각 행, 열, 높이)

 

- 시간복잡도는 O(MNH)이 나온다. 2차원 그래프탐색을 H번 진행해야 하므로!

 

- 처음에 토마토가 담긴 칸을 queue에 담는다. 또, visited를 0으로 설정한다. queue는 2개의 pair가 존재하는데, 1개는 높이와 x좌표, 다른 하나는 y좌표와 해당 칸의 방문 시간을 의미한다.

 

- visited 배열은 해당 칸의 토마토가 익는 최소 시간값을 담는다. 해당 칸이 벽이거나, 처음부터 익은 토마토인 경우 0이 담긴다.

또, BFS를 진행할 때 큐에 담기지 않는 조건은

 

  1. 범위를 벗어날 때

  2. 만약 이미 토마토가 익은 시간이 담겨져 있을 때, 최신화하려는 값이 기존의 시간보다 더 크거나 같은 경우

  3. 벽일때(-1일때)

 

로 잡는다.  

 

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int tomato[101][101][101];
int visited[101][101][101];
int m,n,h;
int dz[] = { 0,0,0,0,1,-1 };
int dx[] = { 0,0,1,-1,0,0 };
int dy[] = { -1,1,0,0,0,0 };
int answer;
queue<pair<pair<int, int>, pair<int, int>>> q;

void BFS() {
	while (!q.empty()) {
		int z = q.front().first.first;
		int x = q.front().first.second;
		int y = q.front().second.first;
		int time = q.front().second.second;
		q.pop();
		for (int k = 0; k < 6; k++) {
			int nz = z + dz[k]; int nx = x + dx[k]; int ny = y + dy[k];
			if (nz < 0 || nz >= h || nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (tomato[nz][nx][ny] == -1) continue;
			if (tomato[nz][nx][ny] == 1 && time + 1 >= visited[nz][ny][nx]) continue;
			visited[nz][nx][ny] = time + 1;
			tomato[nz][nx][ny] = 1;
			q.push({{ nz,nx }, { ny,time + 1 }});
		}
	}
}
int main() {
	cin >> m >> n >> h;
	int num_of_green = 0;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < m; k++) {
				cin >> tomato[i][j][k];
				if (tomato[i][j][k] == 1) {
					q.push({ {i,j}, {k,0} });
				};
				if (tomato[i][j][k] == 0) num_of_green++;
			}
		}
	}
	if (num_of_green == m * n * h) answer = -1;
	else BFS();
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < m; k++) {
				if (visited[i][j][k] == 0 && tomato[i][j][k] == 0) {
					cout << -1;
					return 0;
				}
				answer = max(answer, visited[i][j][k]);
			}
		}
	}
	cout << answer;
	return 0;
}