[백준/7569] 토마토

1. 문제

1) 문제 링크

    : www.acmicpc.net/problem/7569

7569번: 토마토

 

2) 설명

토마토가 다 익는 데 걸리는 시간(처음부터 모두 익어있었다면 0, 다 익을 수 없는 상황이면 -1)을 구하는 문제.

안 익은 토마토 = 0

토마토가 없는 칸 = -1

익은 토마토 = 1

로 주어지고 익은 토마토 주변의 안 익은 토마토들이 익는다.

 

 

2. 풀이

1) 알고리즘

   : BFS

 

2) 풀이 설명

예전에 풀었던 문제지만 다시 한번 풀어봤다.

 

전형적인 BFS문제다.

 

토마토 익을 때까지 큐에 넣다 뺐다 하면서 계속 돌리면 된다.

 

bfs에서 자주 사용하는 visited 배열(방문 확인을 위한)을 사용하지 않은 이유는 0인 칸을 방문하게 되면 (이전 칸 + 1) 값으로 계속 업데이트 해주기 때문에 각 칸이 0일 때만 다음에 방문할 수 있는 칸이 되기 때문이다. 

 

다 돌리고 box에 0(안 익은 토마토)가 남았다면 -1 리턴해주면 된다.

 

처음부터 다 익은 상황이었으면 answer 값이 1이 되므로 마지막에 출력하는 (answer - 1)이 0이 되어서, 모두 잘 익은 상황, 처음부터 모두 익은 상황을 커버할 수 있다.

 

3. 코드

 

/*
	토마토(3차원)
	BFS
	난이도 
*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int answer = 0;
	int M, N, H;
	cin >> M >> N >> H;

	vector<vector<vector<int>>> box(H, vector<vector<int>>(N, vector<int>(M, 0)));
	queue<tuple<int, int, int>> q;
	int dx[6] = {-1, 1, 0, 0, 0, 0};
	int dy[6] = {0, 0, -1, 1, 0, 0};
	int dz[6] = {0, 0, 0, 0, -1, 1};
	
	//입력
	for(int i=0;i<H;i++){
		for(int j=0;j<N;j++){
			for(int k=0;k<M;k++){
				cin >> box[i][j][k];
				if(box[i][j][k] == 1)
					q.push({i, j, k});
			}
		}
	}
	//BFS 시작
	while(!q.empty()){
		int z = get<0>(q.front());
		int x = get<1>(q.front());
		int y = get<2>(q.front());
		q.pop();

		for(int i=0;i<6;i++){
			int nx = x + dx[i];
			int ny = y + dy[i];
			int nz = z + dz[i];

			if(nx<0 || nx>=N || ny<0 || ny>=M || nz<0 || nz>=H)
				continue;
			if(box[nz][nx][ny] != 0)
				continue;
			box[nz][nx][ny] = box[z][x][y] + 1;
			q.push({nz, nx, ny});
		}
	}

	//다 익을 수 없는 경우 체크, 토마토가 익는 데 걸리는 최대 시간 찾기
	for(int i=0;i<H;i++){
		for(int j=0;j<N;j++){
			for(int k=0;k<M;k++){	
				if(box[i][j][k] == 0){
					cout << "-1\n";
					return 0;
				}
				answer = max(answer, box[i][j][k]);
			}
		}
	}
	
	//1부터 셌으니까 -1 해서 출력
	cout << answer - 1 << "\n";

	return 0;
}

 

4. 느낀점

1) 잘 안 다뤄본 3차원 BFS를 하다 보니까 인덱스 설정이 헷갈려서 실수를 많이 했다.

2) 마지막에 안 익은 토마토가 있는지 확인하기 위한 루프를 돌아서 그런지 다른 풀이들보다 시간이 약간 더 걸린다.

   -> 변수가 많아지더라도 시간을 절약하는 것이 좋은지, 가시성과 명확성을 높이기 위해 각 프로세스를 구분하는 게 좋은지 고민해보야 할 것 같다.

3) 3차원 벡터 초기화와 함께 선언하는 게 많이 귀찮다. 더 편한 방법이 있는지 찾아보면 좋을 것 같다.