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

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

7569번: 토마토

 

BFS알고리즘의 입문용 문제인 토마토 입니다. 기존 토마토와 다른점은 2차원배열을 사용한다는 점입니다.

BFS는 큐를 이용해서 문제를 해결합니다. 

 

 

 

 

입문할때 풀었던 코드라, 난잡하지만 BFS에 대해서 이해하시기는 좋을 것이라고 생각합니다. 

아래는 정답코드입니다.

#include <iostream>
#include<cstring>
#include <queue>
using namespace std;
int arr[102][102][102];
int m = 0, n = 0, cnt = 0, h = 0;
queue<int> x;
queue<int> y;
queue<int> z;

void find(void) {

	for (int k = 1; k <= h; k++)
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {

				if (arr[i][j][k] == 1) { x.push(j), y.push(i), z.push(k); }

			}
		}
}
int search(int sized) {
	if (sized == 0) return 0;
	while (sized--) {
		int x_x = x.front();
		int y_y = y.front();
		int z_z = z.front();
		if (arr[y_y - 1][x_x][z_z] == 0) y.push(y_y - 1), x.push(x_x ),z.push(z_z), arr[y_y - 1][x_x][z_z] =1;
		if (arr[y_y + 1][x_x][z_z] == 0) y.push(y_y + 1), x.push(x_x), z.push(z_z), arr[y_y + 1][x_x][z_z] = 1;
		if (arr[y_y][x_x - 1][z_z] == 0) y.push(y_y), x.push(x_x-1), z.push(z_z), arr[y_y ][x_x-1][z_z] = 1;
		if (arr[y_y][x_x + 1][z_z] == 0) y.push(y_y), x.push(x_x + 1), z.push(z_z), arr[y_y][x_x + 1][z_z] = 1;
		if (arr[y_y][x_x][z_z - 1] == 0) y.push(y_y), x.push(x_x ), z.push(z_z - 1), arr[y_y][x_x][z_z - 1] = 1;
		if (arr[y_y][x_x][z_z + 1] == 0) y.push(y_y), x.push(x_x), z.push(z_z + 1), arr[y_y][x_x][z_z + 1] = 1;
		x.pop(), y.pop(), z.pop();
	}
	return 1;
}
int search2() {
	for (int k = 1; k <= h; k++)
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				{
					if (arr[i][j][k] == 0 && arr[i - 1][j][k] == -1 && arr[i + 1][j][k] == -1 && arr[i][j - 1][k] == -1 && arr[i][j + 1][k] == -1)
						if (arr[i][j][k - 1] == -1 && arr[i][j][k + 1] == -1)
							return 1;

				}
			}
		}
	return 0;
}
int main()
{
	memset(arr, -1, sizeof(int) * 102 * 102 * 102);
	cin >> m >> n >> h;
	for (int k = 1; k <= h; k++) {
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				cin >> arr[i][j][k];
	}


	if (search2() == 1) {
		cout << -1 << '\n';
		return 0;
	}
			
		
	find();

	while (1) {
		int sd = x.size();
		if (search(sd) == 0) break;
		cnt++;
	
		
	}
		
	cout << cnt-1 << '\n';
}