백준 7569 토마토

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

 

서론

7576문제에서 z축이 추가된 문제.

 

풀이

BFS를 사용하는 7576과 아이디어는 동일

https://hydroponicglass.tistory.com/14

백준 7576 토마토

 

구현

7576문제와 달리 좌표변수가 3개(x,y,z)인지라 pair를 사용할 수 없게 되었다. 그래서 좌표를 pair가 아닌 구조체로 변경하여 큐에 삽입

 

50번째 줄에서 

if (zz >= 0 && yy >= 0 && xx >= 0 && zz < h && yy < n && xx < m && box[zz][yy][xx] == 0)

는 괜찮으나

if (box[zz][yy][xx] == 0 && zz >= 0 && yy >= 0 && xx >= 0 && zz < h && yy < n && xx < m)

는 box[-1][0][0]이 될 수 있어서 오류발생

 

// c++

#include <iostream>
#include <queue>

using namespace std;

typedef struct {
	int z, y, x;
}st;

int m, n, h;
int box[101][101][101]; // z, y, x
queue<st>q;

void input() {
	cin >> m >> n >> h;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < m; k++) {
				int tmp;
				cin >> tmp;
				if (tmp == 1) {
					q.push({ i, j, k });
					box[i][j][k] = tmp;
				}
				else if (tmp == -1) box[i][j][k] = tmp;
			}
		}
	}
}

int bfs() {
	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 = -1;
	while (!q.empty()) {
		result++;
		int qSize = q.size();
		for (int i = 0; i < qSize; i++) {
			int z = q.front().z;
			int y = q.front().y;
			int x = q.front().x;
			q.pop();
			for (int j = 0; j < 6; j++) {
				int zz = z + dz[j];
				int yy = y + dy[j];
				int xx = x + dx[j];
				if (zz >= 0 && yy >= 0 && xx >= 0 && zz < h && yy < n && xx < m && box[zz][yy][xx] == 0) {
					q.push({ zz, yy, xx });
					box[zz][yy][xx] = 1;
				}
			}
		}
	}
	return result;
}

bool check() {
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < m; k++) {
				if (box[i][j][k] == 0) return false;
			}
		}
	}
	return true;
}

int main() {
	int result = 0;
	input();
	result = bfs();
	if (check() == false) cout << -1;
	else cout << result;
}