알고리즘 2613 토마토

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.

 

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

입력파일의 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N 은 상자의 세로 칸의 수를 나타낸다. 단, 2≤M,N≤1,000 이다.

둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N 개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M 개의 정수로 주어진다.

정수 1 은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1 은 토마토가 들어있지 않은 칸을 나타낸다.

여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다.

만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1 을 출력해야 한다.

큐를 이용한 BFS를 통해 익은 토마토를 큐에 집어넣고, 차례대로 빼면서 상, 하, 좌, 우 토마토 중 안 익은 토마토를 큐에 집어 넣는 식으로 큐가 없어질 때 까지 계산하면 된다. 처음에는 BFS없이 풀었더니 Time Limit이 걸렸다.

큐에 관한건 이전 스택/큐 포스트에 나와있고,

else 부분은 상, 하, 좌, 우를 탐색하여 안 익은 토마토를 찾는 과정이다.

#include 

#define SIZE 1000001

typedef struct tomato{
	int x;
	int y;
	int day;
}TOMATO;


TOMATO queue[SIZE];
int arr[1000][1000];

int M, N; // <=1000
int count;
int index;
int sum=0;
int front = 0, rear = 0;

void enqueue(TOMATO a) {
	queue[rear] = a;
	rear = (rear + 1) % SIZE;
}

TOMATO dequeue() {
	TOMATO data;
	if (front == rear) {
		data.day = -1;
		return data;
	}
	data = queue[front];
	front = (front + 1) % SIZE;
	return data;
}





int main() {

	int i, j;

	int empty = 0;
	scanf("%d %d", &M, &N);
	TOMATO temp,temp2;
	
	count = 0;
	/*
	입력 값을 받는다. 초기 count 값은 0이고 처음에 익은 토마토는 day를 0으로 집어 넣는다. 
	토마토가 비어있는 개수를 empty에 저장한다.
	*/
	for (i = 0; i < N; i++) {
		for (j = 0; j < M; j++) {
			scanf("%d", &arr[i][j]);
			if (arr[i][j] == 1) {
				temp.x = i;
				temp.y = j;
				temp.day = count;
				enqueue(temp);
			}
			else if (arr[i][j] == -1) {
				empty++;
			}
		}
	}



	if (N * M == empty + rear) {	//비어있는 칸의 개수와 익어있는 칸의 개수가 전체 개수와 같으면 이미 다 익어 있으므로 0을 출력

	}

	else {

		while (1) {
			temp = dequeue();
			if (temp.day ==-1) {    //큐가 비어있으면 while문을 종료한다.
				break;
			}
			count = temp.day;
			if (temp.y > 0 && arr[temp.x][temp.y - 1] == 0) {	// 왼쪽의 토마토가 안 익었으면 큐에 집어 넣는다.
				temp2.x = temp.x;
				temp2.y = temp.y - 1;	// 왼쪽이므로 y값을 1 빼준다.
				temp2.day = count + 1;	// 집어 넣는 큐는 다음 날 익기때문에 count에 1을 더해준다.
				enqueue(temp2);
				arr[temp.x][temp.y - 1] = 1;	// 집어넣은 토마토는 미리 익은 걸로 표시
			}

			if (temp.y < M - 1 && arr[temp.x][temp.y + 1] == 0) {	// 오른쪽의 토마토가 안 익었으면 큐에 집어 넣는다.
				temp2.x = temp.x;
				temp2.y = temp.y + 1;	// 오른쪽이므로 y값을 1 더해준다.
				temp2.day = count + 1;	// 집어 넣는 큐는 다음 날 익기때문에 count에 1을 더해준다.
				enqueue(temp2);
				arr[temp.x][temp.y + 1] = 1;	// 집어넣은 토마토는 미리 익은 걸로 표시
			}

			if (temp.x > 0 && arr[temp.x - 1][temp.y] == 0) {	// 위쪽의 토마토가 안 익었으면 큐에 집어 넣는다.
				temp2.x = temp.x - 1;	// 위쪽이므로 x값을 1 빼준다.
				temp2.y = temp.y;
				temp2.day = count + 1;	// 집어 넣는 큐는 다음 날 익기때문에 count에 1을 더해준다.
				enqueue(temp2);
				arr[temp.x - 1][temp.y] = 1;	// 집어넣은 토마토는 미리 익은 걸로 표시
			}

			if (temp.x < N - 1 && arr[temp.x + 1][temp.y] == 0) {	// 아래쪽의 토마토가 안 익었으면 큐에 집어 넣는다.
				temp2.x = temp.x + 1;	// 아래쪽이므로 x값을 1 더해준다.
				temp2.y = temp.y;
				temp2.day = count + 1;	// 집어 넣는 큐는 다음 날 익기때문에 count에 1을 더해준다.
				enqueue(temp2);
				arr[temp.x + 1][temp.y] = 1;	// 집어넣은 토마토는 미리 익은 걸로 표시
			}
			
		}
	}

	/*상자를 탐색하여 아직 안 익은 토마토가 하나라도 있으면 모두 익지 못하는 상황이라 -1을 출력*/
	for (i = 0; i < N; i++) {
		for (j = 0; j < M; j++) {
			if (arr[i][j] == 0) {
				count = -1;
				break;
			}
		}
	}

	printf("%d", count);



	return 0;
}