[BOJ] 7569 - 토마토

안녕하세요.

여행벌입니다.

오늘은 BOJ 7569번 토마토 문제를 풀어보겠습니다.

전형적인 BFS를 이용한 문제인데요! 다만 3차원이라 방향을 다룰게 많다는 점이 특이한 것 같습니다.

---

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

7569번: 토마토

[알고리즘풀이]

BFS 탐색을 이용해서, 순회를 진행하고 익지않은토마토가 있는지 없는지 체크한다.

#include<iostream>
#include<queue>

using namespace std;

int box[100][100][100];

// 위 오 아 왼 윗층 아랫층
int x_d[6] = { -1, 0, 1, 0, 0, 0 };
int y_d[6] = { 0, 1, 0, -1, 0, 0 };
int z_d[6] = { 0, 0, 0, 0, 1, -1 };

int BFS(int, int, int, int, int, int);

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	queue<int> x, y, z, l;
	int r, c, h;
	cin >> c >> r >> h;

	for(int k = 0; k < h; k++)
		for (int i = 0; i < r; i++)
			for (int j = 0; j < c; j++){
				cin >> box[i][j][k];
				if (box[i][j][k] == 1) {
					x.push(i);
					y.push(j);
					z.push(k);
					l.push(0);
				}
			}

	int max = 0;
	while (!x.empty()) {
		int s_x = x.front(), s_y = y.front(), s_z = z.front(), s_l = l.front();
		x.pop(), y.pop(), z.pop(), l.pop();
		for (int i = 0; i < 6; i++) {
			int n_x = s_x + x_d[i];
			int n_y = s_y + y_d[i];
			int n_z = s_z + z_d[i];
			if (0 <= n_x && n_x < r && 0 <= n_y && n_y < c && 0 <= n_z && n_z < h && box[n_x][n_y][n_z] == 0) {
				box[n_x][n_y][n_z] = 1;
				x.push(n_x);
				y.push(n_y);
				z.push(n_z);
				l.push(s_l + 1);
				if (max < s_l + 1)
					max = s_l + 1;
			}
		}
	}
	for (int i = 0; i < r; i++)
		for (int j = 0; j < c; j++)
			for (int k = 0; k < h; k++) 
				if (box[i][j][k] == 0) {
					cout << "-1";
					return 0;
				}
	cout << max;
	return 0;
}

---

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.

혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.

많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다! 

감사합니다.