[백준OJ] 7569번 토마토

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

7569번: 토마토

---

 

 

풀이

1. 입력을 받으면서 토마토부분들을 queue에 push해주고, 익지않은 토마토의 개수를 세어준다.

2. queue에 들어있는 토마토들을 가지고 bfs를 실행해준다. 이때 오늘익은 토마토가 같은날 주변의 다른 익지않은 토마토를 익지 못하게 하기위해, 어제익었던 토마토들만 bfs를 돌리며 날짜를 +1해준다. 또한 토마토들이 익을때마다 익지않은 토마토의 개수를 -1 해준다.

3. bfs를 끝낸뒤, 익지않은 토마토의 개수가 남아있다면 -1을, 아니라면 날짜를 return 해준다.

 

시간복잡도

bfs로 모든 배열을 탐색하므로, O(NMH)가 된다.

 

반응형

 

코드

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

typedef struct node {
	int z,x, y;
}node;

int maze[100][100][100];
int mv[6][3] = { //위아래, 좌우, 상하로 움직임
	{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},
{1,0,0},{-1,0,0}
};
int m, n, h;
int blank;//익지않은 토마토
queue<node> tomato;

void input() {
	cin >> m >> n >> h;

	for (int i = 0; i < h; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < m; k++) {
				cin >> maze[i][j][k];
				if (maze[i][j][k] == 0) blank++;
				if (maze[i][j][k] == 1) tomato.push({ i,j,k });
			}
		}
	}
}

bool isIn(int z, int x, int y) {
	return (z >= 0 && z < h&&x >= 0 && x < n&&y >= 0 && y < m);
}

int bfs() {
	int time = 0;
	while (!tomato.empty()&&blank) {
        //오늘 익은 토마토들이 같은날 다른 토마토를 익게하지 않기위해
        //어제익은 토마토들만을 기준으로 bfs
		int tsize = tomato.size();
		for (int i = 0; i < tsize; i++) {
			int z = tomato.front().z;
			int x = tomato.front().x;
			int y = tomato.front().y;
			tomato.pop();

			for (int d = 0; d < 6; d++) {
				int nz = z + mv[d][0];
				int nx = x + mv[d][1];
				int ny = y + mv[d][2];

				if (isIn(nz, nx, ny) && maze[nz][nx][ny] == 0) {
					maze[nz][nx][ny] = 1;
					blank--;
					tomato.push({ nz,nx,ny });
				}
			}
		}
		time++;
	}
	if (blank) {
		return -1;
	}
	else {
		return time;
	}
}

int main() {
	input();
	cout << bfs() << "\n";
}