백준 7569번 토마토 C++, BFS

리뷰

3차 배열의 BFS문제

 

문제 풀이

1. 3차 배열을 사용해야 하므로 방향을 총 6개를 설정해 줘야 한다. 상, 하, 좌, 우, 위, 아래
2. n, m, h값을 입력받고 3차 배열에 값을 넣어준다. 이때 값이 1일경우 미리 큐에 넣어주면 편하다.
3. bfs를 실행하고 3차 배열의 범위 내를 탐색한다. 나는 다음 좌표가 만약 값이 0인 경우 time + 2를 해주었다.
4. bfs가 종료된 후 토마토가 잘 익었는지 확인해 주어야 한다. flag와 max_val 변수를 각각 0으로 초기화 해줬다.
5. 3차 배열을 돌며 만약 0이 발견되면 flag = 1, break 해준다. 그게 아니라면 max_val에 최대값을 저장해 준다.
6. flag가 1일경우 -1을 출력, 0일 경우 max_val을 2로 나눈 값을 출력해 주면 된다.

 

참고 사항

time에 +2를 해준 이유는 최대 값을 찾을때 1인 경우(원래 있던 익은 토마토)는 배제하기 위해서이다.

 

 

정답 코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int dx[] = { 0, 0, 0, 0, 1, -1 };
int dy[] = { 0, 0, 1, -1, 0, 0 };
int dz[] = { 1, -1, 0, 0, 0, 0 };

int n, m, h;
vector<vector<vector<int>>> lst;

struct pos {
	int z, y, x, time;
};

queue<pos> dq;

void bfs() {
	queue<pos> q = dq;
	while (!q.empty()) {
		pos now = q.front();
		q.pop();
		int cz = now.z, cy = now.y, cx = now.x, ctime = now.time;
		for (int i = 0; i < 6; i++) {
			int nz = cz + dz[i], ny = cy + dy[i], nx = cx + dx[i];
			if (0 <= nz && nz < h && 0 <= ny && ny < n && 0 <= nx && nx < m && lst[nz][ny][nx] == 0) {
				lst[nz][ny][nx] = ctime + 2;
				q.push({ nz, ny, nx, ctime + 2 });
			}
		}
	}
}

int main() {
	cin >> m >> n >> h;
	lst.resize(h, vector<vector<int>>(n, vector<int> (m)));
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < m; k++) {
				int num;
				cin >> num;
				lst[i][j][k] = num;
				if (num == 1) dq.push({ i, j, k, 0 });
			}
		}
	}
	int flag = 0, max_val = 0;
	bfs();
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < m; k++) {
				if (lst[i][j][k] == 0) {
					flag = 1;
					break;
				}
				if (lst[i][j][k] > max_val) {
					max_val = lst[i][j][k];
				}
			}
		}
	}
	if (flag) cout << -1;
	else cout << max_val / 2;
}