백준 7576번 : 토마토

 

 

 

 

 

BFS를 사용한 문제다

고려해야할 부분이 많아서 다소 까다로운 문제였다.

 

 

 

1. 1은 익은 토마토, 0은 안익은 토마토, -1은 토마토가 없음 ( 대각선은 영향을 받지 않는다.)

2. 트리를 생각햇을 때 익을 수 있는것이 다 익어서 트리가 완성 되었을 때의 트리의 레벨 수가 익기까지 걸린 일 수.

3. 익은상태로 시작하는 토마토가 여러개일 수도 있음 (토마토상태 입력받으면서 deque에 1인 토마토 push 필요)

4. 토마토가 비어있는 곳(-1)이 있을 때, 다 익을수도 있고 아닐수도 있음 --> 다익었는지 확인하는 함수 따로 필요

 

 

 

#include <iostream>
#include <deque>
//#include <cstring> //memset
using namespace std;

const int MAX = 1000;

typedef struct {
	int y, x;
}Dir;

Dir moveDir[4] = { {1,0},{-1,0},{0,1},{0,-1} };

int N, M;
int box[MAX][MAX];
deque<pair<int, int>> dq;
int noTomato;

int allTomato(void) {
	int possible = N * M - noTomato;
    
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (box[i][j] == 1) {
				tomato++;
			}
		}
	}

	return tomato == possible;
}


int BFS(void) {

	int day = 0;

	// 처음부터 익힐 수 있는 토마토가 없는 경우
	if (dq.empty())
		return -1;
	
	while (!dq.empty()) {	

		int size = dq.size();

		// 같은 레벨의 토마토만 dq에 존재하는 상태를 만듦
		for (int i = 0; i < size; i++) {	

			int y = dq.front().first;
			int x = dq.front().second;

			// 동서남북으로 덜익은 토마토를 파악 후 dq에 push
			for (int i = 0; i < 4; i++) {
				int nextY = y + moveDir[i].y;
				int nextX = x + moveDir[i].x;

				if (0 <= nextY && nextY < N && 0 <= nextX && nextX < M && box[nextY][nextX] == 0) {
					box[nextY][nextX] = 1;
					dq.push_back(make_pair(nextY, nextX));
				}
			}

			dq.pop_front();

			//익힐 수 있는 토마토를 전부 익혔고 모두 익은 경우
			if (dq.size() == 0 && allTomato()) {
				return day;
			}

			//익힐 수 있는 토마토는 전부 익혔지만 안익은 토마토 존재
			else if (dq.size() == 0 && !allTomato()) {
				return -1;
			}
		}
		day++;
	}
}

int main(void) {

	cin >> M >> N;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> box[i][j];


			// 시작부터 익은 토마토가 여러개일 경우를 위해
			if (box[i][j] == 1) {
				dq.push_back(make_pair(i, j));
			}
			
			//토마토가 없는 칸
			else if (box[i][j] == -1) {
				noTomato++;
			}
		}
	}
	
	if (dq.size() == M * N - noTomato) {
		cout << 0 << endl;	// 모든 토마토가 이미 다 익은 상태
	}

	else {
		int result = BFS();
		cout << result << endl;
	}

	return 0;
	
}