토마토 / 백준 (Baekjoon) / 7576

---

토마토 / 백준 (Baekjoon) / 7576

** 여기서 다루는 알고리즘 문제는 저의 창작 문제가 아닐 경우, 저작권 관련 문제를 방지하고자, 문제의 대략적인 설명 및 요구사항만 소개하고 있습니다. 

** 이 공간에서 공유되는 풀이 및 Source code는 제 개인의 학습 목적이며, 당연히 최선의 정답이 아닙니다. 

** 혹시 더 나은 방법이나 아이디어가 있으신 경우에는, 댓글에 의견을 공유해주시면 감사하겠습니다.

** Source code는 C 언어로 작성되었습니다.

---

알고리즘 분류 및 개요

     - 너비 우선 탐색 (BFS, Breadth First Search)

Input / output

- 입력

 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N 은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

 

- 출력

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

주의 사항

- 전형적인 BFS 문제이지만, 결과 출력 시 예외 조건에 주의해야 합니다. 특히, 토마토가 없는 칸의 경우에 대한 예외처리가 필요합니다.

- 토마토가 없는 칸에 의해서, BFS 탐색 이후에도 익지 않는 토마토가 존재할 수 있음에 유의하여야 합니다.

 

 

NOTE :

 아래에 Test input file을 첨부하였으니, 본인의 풀이가 틀렸을 경우 생각하지 못했던 Corner case가 있는지 확인해 보시기 바랍니다.

 

Source code

---

///////////////////////////////////////////////
// - Baekjoon 7576 : 토마토
// - https://www.acmicpc.net/problem/7576
///////////////////////////////////////////////

#include <stdio.h>

typedef unsigned int	(u32);
typedef unsigned short  (u16);
typedef unsigned char	(u8);

typedef signed int		(s32);
typedef signed short	(s16);
typedef signed char		(s8);

#define	MAX_INPUT_SIZE	(1000)

typedef enum _tag_TOMATO{
	EMPTY	= -1,
	GREEN	= 0,
	RED		= 1
}__TOMATO;

// -- Global variables

// Input
u32 g_width, g_height;
__TOMATO input_buf[MAX_INPUT_SIZE][MAX_INPUT_SIZE];

// BFS - Queue
typedef struct _tag_POSITION {
	u32 pos_x;
	u32 pos_y;
}__POS;

u32 Q_front_flag;
u32 Q_rear_flag;

__POS Q_tomato[MAX_INPUT_SIZE * MAX_INPUT_SIZE];

#define ENQUEUE(x, y, Q_pos)	do { Q_tomato[Q_pos].pos_x = (u32)x; Q_tomato[Q_pos].pos_y = (u32)y; Q_pos++; } while(0)
#define DEQUEUE(x, y, Q_pos)	do { x = Q_tomato[Q_pos].pos_x; y = Q_tomato[Q_pos].pos_y; Q_pos++; } while(0)

// BFS - visit buf
u8 visit_buf[MAX_INPUT_SIZE][MAX_INPUT_SIZE];

// Result
u32 g_date;

static void SetInputBuffer( void )
{
	u32 i, j;

	scanf("%d %d", &g_width, &g_height);

	for (i = 0; i < g_height; i++)
	{
		for (j = 0; j < g_width; j++)
		{
			s32 temp_data;
			scanf(" %d", &temp_data);

			input_buf[i][j] = (__TOMATO)temp_data;

			if (input_buf[i][j] == RED)
			{
				ENQUEUE(j, i, Q_rear_flag);
				visit_buf[i][j] = 1;
			}
		}
	}
}

static __inline void CheckUnvisitedGreenTomato( s32 pos_x, s32 pos_y )
{
	if ((visit_buf[pos_y][pos_x] == 0) && (input_buf[pos_y][pos_x] == GREEN))
	{
		input_buf[pos_y][pos_x] = RED;
		ENQUEUE(pos_x, pos_y, Q_rear_flag);
		visit_buf[pos_y][pos_x] = 1;
	}
}

static void TomatoBFS( s32 pos_x, s32 pos_y )
{
	if (pos_y + 1 < g_height)	CheckUnvisitedGreenTomato( pos_x, pos_y + 1 );
	if (pos_y >= 1)				CheckUnvisitedGreenTomato( pos_x, pos_y - 1 );
	if (pos_x + 1 < g_width)	CheckUnvisitedGreenTomato( pos_x + 1, pos_y );
	if (pos_x >= 1)				CheckUnvisitedGreenTomato( pos_x - 1, pos_y );
}

static u32 CheckFullRedTomato( void )
{
	u32 i, j;

	for (i = 0; i < g_height; i++)
	{
		for (j = 0; j < g_width; j++)
		{
			if (input_buf[i][j] == GREEN)
			{
				return 0;
			}
		}
	}

	return 1;
}

static __inline void PrintResult( void )
{
	if (CheckFullRedTomato())
	{
		printf("%d", (g_date - 1));
	}
	else
	{
		printf("-1");
	}
}

s32 main(void)
{
	u32 bound_for_tomorrow = 0;

	SetInputBuffer();
	bound_for_tomorrow = Q_rear_flag;

	if (Q_rear_flag > 0)
	{
		do {
			u32 curr_pos_x, curr_pos_y;

			DEQUEUE(curr_pos_x, curr_pos_y, Q_front_flag);
			TomatoBFS(curr_pos_x, curr_pos_y);

			if (Q_front_flag == bound_for_tomorrow)	
			{
				bound_for_tomorrow = Q_rear_flag;
				g_date++;
			}
		} while (Q_front_flag < Q_rear_flag);
	}
	
	PrintResult();

	return 0;
}

---

난이도 / 중요도 / 재시도

  ★★★☆☆ / ★★★★☆ / x 1

출처 / 관련 링크

- Baekjoon online judge : https://www.acmicpc.net/problem/7576

- BFS Algorithm 소개 : http://jayce-with.tistory.com/9

Test input file

input_sample.txt