[백준] 7576 - 토마토

www.acmicpc.net/problem/7576

7576번: 토마토

• 미로 탐색을 살짝 응용한 문제
• 풀면서 주의했던 점은 미로 탐색은 100이 MAX_SIZE 였으나, 이 문제는 1000 이라 vector<> 사용해서 구성.
• 또한, 같은 날짜에 모든 '1'의 값을 가진 곳에서 상,하,좌,우 확장이 된다.
• 176ms 의 시간이 걸렸지만 80ms도 있는 것을 봐선 더 개선할 수 있다.

---

• 코드

#include <iostream>
#include <vector>
#include <queue>

// def
#define MAX_BOARD_SIZE 1000
#define POS_PAIR std::pair<int, int>
#define DAY_PAIR std::pair<POS_PAIR, int>
#define DEBUG_MODE 0

// struct
struct DATA
{
	DATA()
	{
		data = 0;
		visited = false;
	}
	int data;
	bool visited;
};

// global
/*
* 1 : 익은 토마토
* 0 : 익지 않은 토마토
* -1 : 토마토가 들어 있지 않은 칸
*/
std::vector<DATA> board[MAX_BOARD_SIZE + 1];

// 상 하 좌 우
int direction[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

// method
bool Checking(int x, int y, int X, int Y);
int BFS_Function(int N, int M, int zeroCnt);

int main()
{
	// 7576 - 토마토
	std::ios::sync_with_stdio(false);

	// input
	int N, M;
	N = M = 0;
	(void)scanf("%d %d", &M, &N);
	
	int zeroCnt = 0;
	for (int n = 0; n < N; n++)
	{
		for (int m = 0; m < M; m++)
		{
			DATA tomato;
			(void)scanf("%d", &tomato.data);
			if (0 == tomato.data)
				zeroCnt++;

			board[n].push_back(tomato);
		}
	}

#if DEBUG_MODE
	printf("[%s] zeroCount : %d\n", __FUNCTION__, zeroCnt);
#endif

	// calc
	const int answer = BFS_Function(N, M, zeroCnt);
	printf("%d", answer);

	return 0;
}

bool Checking(int x, int y, int X, int Y)
{
	if ((x < 0 || x >= X) || (y < 0 || y >= Y))
		return false;
	
	return true;
}

int BFS_Function(int N, int M, int zeroCnt)
{
	int retValue = 0;

	if (0 == zeroCnt)
		return retValue;
	
	std::queue<DAY_PAIR> que;
	
	int row, col;
	row = col = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (1 == board[i][j].data)
			{
				que.push(DAY_PAIR(POS_PAIR(i, j), 0));
			}
		}
	}

#if DEBUG_MODE
	printf("[%s] start row : %d, col : %d \n", __FUNCTION__, row, col);
#endif

	int count = 0;
	int max = 0;
	while (!que.empty())
	{
		DAY_PAIR dayPair = que.front();
		que.pop();
		POS_PAIR pos = dayPair.first;
		int day = dayPair.second;
		max = max > day ? max : day;
		
		for (int d = 0; d < 4; d++)
		{
			int x = pos.first - direction[d][0];
			int y = pos.second - direction[d][1];

			const bool bIsValid = Checking(x, y, N, M);
			if (true == bIsValid)
			{
				if (false == board[x][y].visited && -1 != board[x][y].data)
				{
					que.push(DAY_PAIR(POS_PAIR(x, y), day+1));
					board[x][y].visited = true;
					if (0 == board[x][y].data)
					{
						board[x][y].data = 1;
						count++;
					}
#if DEBUG_MODE
					printf("----pos (%d, %d, %d) | x : %d, y : %d, day+1 : %d ----\n",
						pos.first, pos.second, day, x, y, day+1);
#endif
				}
			}
			else
				continue;
		}
	}

	if (count != zeroCnt)
		retValue = -1;
	else
		retValue = max;

	return retValue;
}

---

• 128ms 까지 속도를 개선해보았다.
  1. #if DEBUG_MODE ~~~ #endif 삭제
  2. std::cin, std::cout 사용 (실무에서는 scanf 나 printf 사용할 것)
  3. 입력 loop에서 '1'이 나올때 처음 bfs que에 들어갈 데이터 정리.
  4. max 필요없이 DAY_PAIR의 2번째 값을 retValue로 계속 업데이트.
  5. 115 line의 else continue; 를 없애면 속도가 떨어졌었다.
  6. struct DATA를 없애고 std::vector<int> [], bool []로 분리 -> 메모리 사용량 감소.
• 코드

#include <iostream>
#include <vector>
#include <queue>

// def
#define MAX_BOARD_SIZE 1000
#define POS_PAIR std::pair<int, int>
#define DAY_PAIR std::pair<POS_PAIR, int>
#define DEBUG_MODE 0

// global
/*
* 1 : 익은 토마토
* 0 : 익지 않은 토마토
* -1 : 토마토가 들어 있지 않은 칸
*/
std::vector<int> board[MAX_BOARD_SIZE + 1];
bool visited[MAX_BOARD_SIZE + 1][MAX_BOARD_SIZE+1];

// 상 하 좌 우
int direction[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

// method
bool Checking(int x, int y, int X, int Y);
int BFS_Function(int N, int M, int zeroCnt, std::vector<POS_PAIR>& startList);

int main()
{
	// 7576 - 토마토
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);

	// input
	int N, M;
	N = M = 0;
	std::cin >> M >> N;
	
	int zeroCnt = 0;
	std::vector<POS_PAIR> startList;
	for (int n = 0; n < N; n++)
	{
		for (int m = 0; m < M; m++)
		{
			int tomato;
			std::cin >> tomato;
			
			if (0 == tomato)
				zeroCnt++;
			else if (1 == tomato)
				startList.push_back(POS_PAIR(n, m));

			board[n].push_back(tomato);
		}
	}

	// calc
	const int answer = BFS_Function(N, M, zeroCnt, startList);
	std::cout << answer;

	return 0;
}

bool Checking(int x, int y, int X, int Y)
{
	if ((x < 0 || x >= X) || (y < 0 || y >= Y))
		return false;
	
	return true;
}

int BFS_Function(int N, int M, int zeroCnt, std::vector<POS_PAIR>& startList)
{
	int retValue = 0;

	if (0 == zeroCnt)
		return retValue;
	
	std::queue<DAY_PAIR> que;
	for (POS_PAIR& data : startList)
	{
		que.push(DAY_PAIR(data, 0));
		visited[data.first][data.second] = true;
	}

	int count = 0;
	while (!que.empty())
	{
		DAY_PAIR dayPair = que.front();
		que.pop();

		POS_PAIR pos = dayPair.first;
		int day = dayPair.second;
		retValue = day;
		
		for (int d = 0; d < 4; d++)
		{
			int x = pos.first - direction[d][0];
			int y = pos.second - direction[d][1];

			const bool bIsValid = Checking(x, y, N, M);
			if (true == bIsValid)
			{
				if (false == visited[x][y] && -1 != board[x][y])
				{
					que.push(DAY_PAIR(POS_PAIR(x, y), day+1));
					visited[x][y] = true;
					
					if (0 == board[x][y])
					{
						board[x][y] = 1;
						count++;
					}
				}
			}
			else
				continue;
		}
	}

	if (count != zeroCnt)
		retValue = -1;

	return retValue;
}