[C++][백준 7576][BFS / DFS] 토마토 :: seoftware

문제

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

7576번: 토마토

소스코드

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int N, M;
int tomato[1001][1001];
bool visited[1001][1001];
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };

int main(void) {
	//input
	cin >> M >> N;
	queue<pair<int, int>> q;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> tomato[i][j];
			if (tomato[i][j] == 1) {
				q.push({ i, j });
			}
		}
	}

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		visited[x][y] = true;
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && ny >= 0 && nx < N && ny < M && tomato[nx][ny] == 0 && !visited[nx][ny]) {
				tomato[nx][ny] = tomato[x][y] + 1;
				q.push({ nx, ny });
			}
		}
	}

	int max = -1; 
	bool allRipe = true;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (tomato[i][j] == 0) {
				allRipe = false;
			}
			if (tomato[i][j] > max) {
				max = tomato[i][j];
			}
		}
	}

	if (allRipe) cout << max - 1 << endl;
	else cout << -1 << endl;

	return 0;
}

BFS 문제 유형 중에 이런게 많은 것 같다. 내가 온 곳의 값을 활용하는 문제!

만약 tomato[1][1]에서 tomato[1][2]로 간 경우에는 tomato[1][1]+1 한 값을 tomato[1][2]에 저장한다.

위의 방법을 이용하기 전에는 재귀를 사용했었다. bfs 함수를 만들고 큐를 두 개 사용해서 한 큐가 bfs 함수를 수행하고 나면 수행하는 동안 쌓인 새로운 큐로 다시 bfs 문을 수행한다. 그렇게 하면 재귀함수를 호출하는 횟수만큼 날이 지났다고 판단 할 수 있기 때문이다. 그러나 메모리 초과가 나서 새로운 방법을 생각할 수 밖에 없었다.

아래는 메모리 초과가 났던 재귀를 사용한 코드이다.

#include <iostream>
#include <queue>

using namespace std;

int N, M;
int tomato[1000][1000];
bool visited[1000][1000];
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };
int cnt;

void bfs(queue<pair<int, int>> &q1) {
	cnt++;
	queue<pair<int, int>> q2;
	while (!q1.empty()) {
		int x = q1.front().first;
		int y = q1.front().second;
		q1.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx >= 0 && ny >= 0 && nx < N && ny < M && tomato[nx][ny] == 0 && !visited[nx][ny]) {
				visited[nx][ny] = true;
				tomato[nx][ny] = 1;
				q2.push({ nx, ny });
			}
		}
	}
	if(!q2.empty()) bfs(q2);
}

int main(void) {
	//input
	cin >> M >> N;

	queue<pair<int, int>> q1;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> tomato[i][j];
			if (tomato[i][j] == 1) {
				q1.push(make_pair(i, j));
				visited[i][j] = true;
			}
		}
	}
	q1.front();
	//peform
	cnt = 0;
	if (!q1.empty()) {
		bfs(q1);
	}
	
	bool allRipe = true;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (tomato[i][j] == 0) {
				allRipe = false;
				break;
			}
		}
	}

	if (allRipe) cout << cnt - 1 << endl;
	else cout << -1 << endl;

	return 0;
}