2023.02.05.(일)

문제

problem

접근 방법

저는 BFS를 사용해서 이 문제를 해결하기로 했습니다. 어느 토마토를 기준으로 위, 아래, 앞, 뒤, 왼쪽, 오른쪽을 먼저 모두 살펴 보아야 하기 때문입니다. BFS는 스택이 아닌 큐를 사용합니다. r, c, h, total이라는 이름의 큐들을 만듭니다.

r은 행의 인덱스, c는 열의 인덱스, h는 층의 인덱스를 뜻합니다. 토마토가 있는 상자는 box라는 삼차원 배열로 표현하구요. 처음에 상자에서 익어 있는 토마토가 있는 좌표들을 미리 이 큐들에 넣어둡니다.

토마토 하나를 기준으로 위, 아래, 앞, 오른쪽, 뒤, 왼쪽을 확인하여(box[r.front()][c.front()][h.front()]) 익지 않은 토마토가 있으면 값을 0에서 1로 바꾸어 토마토가 익었음을 나타내고, 각 좌표들을 큐에 순서대로 넣습니다. total 큐에는 total.front()+1 을 해주어, 현재 토마토가 처음 토마토로부터 익은 날짜의 1일 후에 익을 것임을 표현합니다. 모든 방향을 확인했으면 큐에서 각 값들을 뺀 후에 위 과정을 반복합니다. total 큐에 아무 값도 남지 않을 때까지요!!

코드

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

int main()
{
	int box[101][101][101] = {0}; 
	int M, N, H; 

	cin >> M >> N >> H; 

	int num; 
	queue<int> r, c, h, total;

	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= N; j++) {
			for (int k = 1; k <= M; k++) {
				cin >> num; 
				if (num == 1) {
					h.push(i); 
					r.push(j);
					c.push(k);
					total.push(0);  
				}
				box[i][j][k] = num; 
			}
		}
	}

	// total.push(0);   ---> total에 0을 한 번만 추가하면 안됩니다. 
    // 처음에 상자에서 익어 있는 토마토 수만큼 추가해 주어야 하죠. 
	int day = 0; 
	while (!total.empty()) {
		// 위, 아래, 앞, 우, 뒤, 좌
		if (h.front()-1 >= 1 && box[h.front()-1][r.front()][c.front()] == 0) {
			// 위
			h.push(h.front()-1); 
			r.push(r.front());
			c.push(c.front()); 
			total.push(total.front()+1); 
			box[h.front()-1][r.front()][c.front()] = 1;
		}
		if (h.front()+1 <= H && box[h.front()+1][r.front()][c.front()] == 0) {
			// 아래
			h.push(h.front()+1); 
			r.push(r.front());
			c.push(c.front()); 
			total.push(total.front()+1);
			box[h.front()+1][r.front()][c.front()] = 1;
		}
		if (r.front()-1 >= 1 && box[h.front()][r.front()-1][c.front()] == 0) {
			// 앞
			h.push(h.front()); 
			r.push(r.front()-1);
			c.push(c.front()); 
			total.push(total.front()+1);
			box[h.front()][r.front()-1][c.front()] = 1;
		}
		if (c.front()+1 <= M && box[h.front()][r.front()][c.front()+1] == 0) {
			// 우
			h.push(h.front()); 
			r.push(r.front());
			c.push(c.front()+1);
			total.push(total.front()+1); 
			box[h.front()][r.front()][c.front()+1] = 1;
		}
		if (r.front()+1 <= N && box[h.front()][r.front()+1][c.front()] == 0) {
			// 뒤
			h.push(h.front()); 
			r.push(r.front()+1);
			c.push(c.front()); 
			total.push(total.front()+1);
			box[h.front()][r.front()+1][c.front()] = 1;
		}
		if (c.front()-1 >= 1 && box[h.front()][r.front()][c.front()-1] == 0) {
			// 좌
			h.push(h.front()); 
			r.push(r.front());
			c.push(c.front()-1); 
			total.push(total.front()+1);
			box[h.front()][r.front()][c.front()-1] = 1;
		}
		if (total.front() > day) {
			day = total.front(); 
		}
		h.pop(); r.pop(); c.pop(); total.pop(); 
	}

	// 만약 상자에 익지 않은 토마토가 남아 있다면 -1 출력 후 프로그램 종료.
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= N; j++) {
			for (int k = 1; k <= M; k++) {
				if (box[i][j][k] == 0) {
					cout << -1;
					return 0;  
				}
			}
		}
	}
	cout << day; 
	return 0; 
}