[BOJ] 7569번: 토마토

문제 링크: 백준/BOJ https://www.acmicpc.net/problem/7569

7569번: 토마토

 

처음 bfs에 입문했을 때 풀었던 문제다.

상차가 h층만큼 존재하기 때문에 1층만 있는 문제와 다른점은 한 지점에서 이동할 수 있는 방향이다.

2차원에서와 다르게 위, 아래로도 이동할 수 있으므로 총 6가지 방향에 대한 배열을 선언해주었다.

 

개인적으로 tuple을 사용하면 값에 대한 접근 방식이 귀찮아서 구조체를 더 애용하는 편이다.

 

 

/*
20200413
baekjoon 7569번 토마토
*/
#include <iostream>
#include <queue>
#include <tuple>
using namespace std;

int n, m, h;  int graph[100][100][100]; int dx[6] = { 0,1,0,-1,0,0 }, dy[6] = { 1,0,-1,0,0,0 }, dz[6] = { 0,0,0,0,1,-1 };
bool visited[100][100][100];
struct tomato {
public:
	int x, y, z;
};

bool isInRange(int r, int c, int z) {
	return r >= 0 && r < n && c >= 0 && c < m&&z >= 0 && z < h;
}

int main() {
	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
	cin >> m >> n >> h;

	int zeroCnt = 0;
	queue<tomato>q;
	for (int i = 0; i < h; ++i) {
		for (int j = 0; j < n; ++j) {
			for (int k = 0; k < m; ++k) {
				cin >> graph[j][k][i];
				if (graph[j][k][i] == 0) {
					zeroCnt++;
				}
				else if (graph[j][k][i] == 1) {
					visited[j][k][i] = 1;
					q.push({ j,k,i });
				}
			}
		}
	}

	if (zeroCnt == 0) {
		cout << 0;
		return 0;
	}

	int ans = 0; bool found = false;
	while (!q.empty()) {
		int sz = q.size();
		while (sz--) {
			int cX = q.front().x, cY = q.front().y, cZ = q.front().z;
			q.pop();
			for (int i = 0; i < 6; ++i) {
				int nX = cX + dx[i], nY = cY + dy[i], nZ = cZ + dz[i];
				if (!isInRange(nX, nY, nZ) || visited[nX][nY][nZ]) continue;
				if (graph[nX][nY][nZ] == 0) {
					visited[nX][nY][nZ] = 1;
					q.push({ nX,nY,nZ });
					zeroCnt--;
					if (zeroCnt == 0) {
						found = true;
						break;
					}
				}
			}
			if (found) break;
		}
		ans++;
		if (found) break;
	}

	if (found) cout << ans;
	else cout << -1;
}