C++ / 백준 / 7569 / 토마토

문제

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

7569번: 토마토

문제풀이

토마토 문제를 아직 안 풀었다면 7576번 먼저 푸는 것을 추천함.

7576번은 2차원, 7569번은 3차원 문제

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

3차원 배열을 거의 안 쓰다 보니 그 부분에서 좀 헤맸다.

 

입력받을 때 토마토가 0or1이면 도달해야 되는 토마 토수 +1,

1이면 현재 익은 토마토 수 +1, 큐에 좌표값을 집어넣고

큐가 빌 때까지 반복, 이동할 수 있으면 큐에 넣고 지난날+1을 한다.

토마토가 도달해야 되는 값에 도달했으면 day값을 리턴,

도달 못했으면 -1을 리턴한다.

vector<vector<vector<int>>>tomato;
queue<vector<int>>ripen;
vector<vector<vector<int>>>spread = { {{0,-1,0}},{{0,1,0}},{{0,0,1}},{{0,0,-1}},{{1,0,0}},{{-1,0,0}} };
int M, N, H;
int z, y, x;
int day;
int total;
int now;

3차원 벡터 tomato를 선언한다. 현재 판에 토마토들의 상태를 나타내는 배열이다.

ripen은 큐로, 큐 안에 벡터를 넣어 (z좌표, y좌표, x좌표, 지난날)을 나타내는 큐이다.

spread는 한 칸 이동할 수 있는 앞, 뒤, 상, 하, 좌, 우 좌표를 나타낸 벡터이다.

total은 총 익어야 되는 토마토 수, 0 or 1이면 +1, now는 현재 익은 토마토 수를 나타내는 변수이다.

 

while (!ripen.empty()) {
		z = ripen.front()[0];
		y = ripen.front()[1];
		x = ripen.front()[2];
		day = ripen.front()[3];
		ripen.pop();
		for (int cnt = 0; cnt < 6; ++cnt) {
			int n_z = z + spread[cnt][0][0];
			int n_y = y + spread[cnt][0][1];
			int n_x = x + spread[cnt][0][2];
			int n_day = day + 1;
			if (n_z >= 0 && n_z < H && n_y >= 0 && n_y < N && n_x >= 0 && n_x < M) {
				if (tomato[n_z][n_y][n_x] == 0) {
					ripen.push({ n_z, n_y, n_x, n_day });
					tomato[n_z][n_y][n_x] = 1;
					now++;
				}
			}
		}
	}

z는 z좌표, y는 y좌표, x는 x좌표, day는 지난날로 큐에 4칸 있는 벡터에서 정보를 불러온다.

큐에서 정보를 불러왔으니 pop 하여 지운다.

n_좌표 값들에 이동할 수 있는 좌표를 더해 좌표가 범위 안에 들고, 이동할 칸의 토마토가 익지 않았다면

1로 표시하여 익히고, 큐에 push 하고 익은 토마토 수에 +1을 한다.

 

 

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<vector<vector<int>>>tomato;
queue<vector<int>>ripen;
vector<vector<vector<int>>>spread = { {{0,-1,0}},{{0,1,0}},{{0,0,1}},{{0,0,-1}},{{1,0,0}},{{-1,0,0}} };
int M, N, H;
int z, y, x;
int day;
int total;
int now;

int Storage() {
	while (!ripen.empty()) {
		z = ripen.front()[0];
		y = ripen.front()[1];
		x = ripen.front()[2];
		day = ripen.front()[3];
		ripen.pop();
		for (int cnt = 0; cnt < 6; ++cnt) {
			int n_z = z + spread[cnt][0][0];
			int n_y = y + spread[cnt][0][1];
			int n_x = x + spread[cnt][0][2];
			int n_day = day + 1;
			if (n_z >= 0 && n_z < H && n_y >= 0 && n_y < N && n_x >= 0 && n_x < M) {
				if (tomato[n_z][n_y][n_x] == 0) {
					ripen.push({ n_z, n_y, n_x, n_day });
					tomato[n_z][n_y][n_x] = 1;
					now++;
				}
			}
		}
	}
	if (now == total) {
		return day;
	}
	else  return -1;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> M >> N >> H;
	tomato = vector<vector<vector<int>>>(H, vector<vector<int>>(N, vector<int>(M, 0)));

	for (z = 0; z < H; ++z) {
		for (y = 0; y < N; ++y) {
			for (x = 0; x < M; ++x) {
				cin >> tomato[z][y][x];
				if (tomato[z][y][x] == 1) ripen.push({ z,y,x,0 });
				if (tomato[z][y][x] == 0 || tomato[z][y][x] == 1) total++;
				if (tomato[z][y][x] == 1) now++;
			}
		}
	}
	cout << Storage();
}