백준 7569번: 토마토 (C++)

문제 링크이다. 

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

7569번: 토마토

 

두 번째 토마토 문제이다.

 

첫번째 토마토 문제와 동일하지만 높이 조건이 추가되었다. 차원이 하나 더 추가된 것이다.

 

다만 2차원 상황일 때는 queue에 pair 자료구조를 넣어서 활용했다.

 

이번에는 세개라서 간단하게 구조체를 선언해서 활용했다.

 

또한 점의 움직임을 정의하는 배열도, 동서남북 이외에 위아래가 추가되었기 때문에 크기를 6으로 잡아주고, 높이 움직임을 처리할 배열을 추가해주었다.

 

마찬가지로 update가 되지 않은 경우에는 큐가 비어있지 않아도 수행을 마치게 하였다.

 

 

여담으로, 삼성 소프트웨어 역량테스트 A형의 경우, 여러개의 테스트 케이스를 처리해야 하기때문에 초기화가 중요하다.

 

이 상황을 가정하고 코드를 정리하던 도중, 큐가 비어있지 않은 상태로 다음 테스트 케이스에서 이용할 수 있는 여지가 있다는 것을 생각해냈다.

 

따라서 초기화를 해줄 때에는, 단순히 전역변수로 사용한 여러가지 변수들과 더불어서, 큐 또한 비워주는 방식의 초기화를 해줘야 할 것이다.

 

아래 코드는 한 개의 테스트 케이스만 처리하면 될 때의 코드이다.

 

#include<iostream>
#include<queue>
using namespace std;
int col, row, H, m[100][100][100];
bool vis[100][100][100];
struct pt {
	int h;
	int row;
	int col;
};
queue<pt> q;
int dh[6] = { 0,0,0,0,1,-1 };
int dr[6] = { 0,0,1,-1,0,0 };
int dc[6] = { 1,-1,0,0,0,0 };
int Day = 0;
bool updated = false;

void bfs() {
	while (!q.empty()) {
		int cnt = q.size();
		updated = false;
		while (cnt--) {
			pt cur = q.front();
			q.pop();
			for (int i = 0; i < 6; i++) {
				int nh = cur.h + dh[i];
				int nr = cur.row + dr[i];
				int nc = cur.col + dc[i];
				
				if (nh < 0 || nr < 0 || nc < 0 || nh >= H || nr >= row || nc >= col) continue; //범위 밖이면 pass
				if (m[nh][nr][nc] != 0 || vis[nh][nr][nc]) continue; //토마토가 익지 않은 자리가 아니거나 이미 방문한 지점이면 pass
				
				m[nh][nr][nc] = 1;
				q.push({ nh, nr, nc });
				vis[nh][nr][nc] = true;
				updated = true;
			}
		}
		if (!updated) break; //하루 지났는데 변화가 없었으면 break;
		Day++;
	}
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
		cin >> col >> row >> H;

		for (int h = 0; h < H; h++) {
			for (int i = 0; i < row; i++) {
				for (int j = 0; j < col; j++) {
					cin >> m[h][i][j];
					if (m[h][i][j] == 1) {
						q.push({ h, i, j });
						vis[h][i][j] = true;
					}
				}
			}
		}
		bfs();
		for (int h = 0; h < H; h++) {
			for (int i = 0; i < row; i++) {
				for (int j = 0; j < col; j++) {
					if (m[h][i][j] == 0) {
						cout << -1 << '\n';
						return 0;
					}
				}
			}
		}
		cout << Day << '\n';
	return 0;
}