BOJ-7576 토마토

https://www.acmicpc.net/problem/7576

문제 소개

토마토가 담긴 상자의 크기를 나타내는 두 정수 M, N과 상자의 각 칸에 담긴 토마토의 정보가 주어진다.

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

상자에서는 하루가 지날 때마다 익은 토마토와 인접한 익지 않은 토마토들이 익게 된다. 이때 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향을 의미한다.

토마토가 모두 익는데까지 걸리는 최소 일수를 출력하라.

만약 모든 토마토가 최초에 익어있는 상태라면 0을 출력하고, 토마토가 모두 익을 수 없다면 -1을 출력하라.

문제 풀이

아래 과정을 통해 동작한다.

1. current와 next라는 두 개의 큐를 둔 후, 최초 익어있는 토마토를 current에 담는다.

2. 하루동안 익는 토마토를 탐색하여 next에 담고 current의 모든 토마토에 대해 탐색을 완료하면 일수를 1 증가시키고 next의 내용을 current에 복사한다.

3. next에 토마토가 담기지 않을 때까지 current에 있는 토마토에 대한 탐색을 반복한다.

이때의 탐색은 함수 search()로 수행하며, bfs를 한 사이클 수행하는 효과이다.

함수 count_unripe()는 익지 않은 토마토의 개수를 세는 함수이다. 모든 토마토가 최초에 익어있거나 토마토가 모두 익을 수 없는 상태를 판별하기 위해 사용한다.

코드

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

int dx[4] = { 0, -1, 0, 1 };
int dy[4] = { -1, 0, 1, 0 };

typedef std::vector<std::vector<int>> box_t;
typedef std::queue<std::pair<int, int>> pending_t;

void search(int start_x, int start_y, int n, int m, box_t& arr, pending_t& next) {
	for (int i = 0; i < 4; i++) {
		int nx = start_x + dx[i];
		int ny = start_y + dy[i];
		if (0 <= nx && nx < n && 0 <= ny && ny < m && arr[nx][ny] == 0) {
			next.push({ nx, ny });
			arr[nx][ny] = 1;
		}
	}
}

int count_unripe(box_t& arr, int n, int m) {
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr[i][j] == 0) {	// 익지 않은 경우
				cnt += 1;
			}
		}
	}
	return cnt;
}

int main() {
	using namespace std;
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int m, n;
	cin >> m >> n;

	box_t arr(n, vector<int>(m, 0));
	pending_t current;

	// 초기 current 설정
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int t;
			cin >> t;
			arr[i][j] = t;
			if (t == 1) {
				current.push({ i, j });
			}
		}
	}

	// 저장될 때부터 모든 토마토가 익어있다면
	if (!count_unripe(arr, n, m)) {
		cout << 0 << "\n";
	}
	else {
		int day = 0;
		while (1) {
			pending_t next;
			while (!current.empty()) {
				pair target = current.front();
				search(target.first, target.second, n, m, arr, next);
				current.pop();
			}

			// 더 이상 탐색할 수 없다면
			if (next.empty()) {
				break;
			}
			// 탐색이 더 가능하다면 날짜를 1 증가시키고 next의 내용을 current에 복사
			else {
				day += 1;
				current = pending_t(next);
			}
		}

		// 안 익은 토마토가 존재한다면
		if (count_unripe(arr, n, m)) {
			cout << -1 << "\n";
		}
		// 모두 익었다면
		else {
			cout << day << "\n";
		}
	}

	return 0;
}