백준 7576번 토마토(C++)

예전에 풀었던 문제이지만 다시한 번 해보았다. 예전의 코드는 구글링의 다른 사람의 코드를 도움 받았기 때문이다. 그리고 BFS의 좋은 예제이다.

 

먼저 토마토 1이 있으면 하루에 4방향으로 증식한다. 증식한 토마토는 또 4방향으로 증식하게된다. DFS로 계산하면 한 방향으로만 가버리기 때문에 적절하지 않다. 결국 BFS를 통해 첫 1부터 제일 떨어져 있는 거리까지의 최소거리(최소일수)를 구하는 문제로 귀결된다. 그러나 여기서 중요한 것은 1이 한군데만 존재하지 않는다는 것이다. 즉, 두군데 이상의 1에서 동시에 증식을 시작해야한다. 그림으로 표현하면

 

이런식이다. 때문에 DFS는 절대(적어도 내 기준에선) 사용할 수 없다.

 

알고리즘은 이러하다.

1. 처음 토마토가 심어져 있는 좌표를 큐에 삽입.

2. 삽입된 큐를 가지고 BFS 순회하며 0인 좌표들로 증식, dis배열에 1부터의 거리 저장

3. 모든 순회가 끝났는데 0인지점이 존재한다면 -1로 둘러쌓인 곳이 있는 것임 => -1 출력

4. dis에서 가장 큰 수가 최소일수이므로 max를 구해 출력

 

이전에도 거의 같은 방식으로 풀긴했다. 아마 이전 풀이엔 쓸데없는 조건이 몇개 들어있는 것 같다. 메모리도 조금 줄었고 시간도 대폭 개선되었다.

 

#include<iostream>
#include<algorithm>
#include<queue>

#define MAX 1001

using namespace std;

int M, N;

int tomato[MAX][MAX];
int dis[MAX][MAX] = {0,};

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

int cnt = 0;
queue<pair<int, int>> bfsq;

void BFS() {
	while (!bfsq.empty()) {
		int x = bfsq.front().first;
		int y = bfsq.front().second;

		bfsq.pop();

		for (int i = 0; i < 4; i++) {
			int xn = x + dx[i];
			int yn = y + dy[i];

			if (xn > -1 && xn < N && yn > -1 && yn < M && tomato[xn][yn] == 0) {
				bfsq.push(make_pair(xn, yn));
				tomato[xn][yn] = 1;
				dis[xn][yn] = dis[x][y] + 1;
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	cin >> M >> N;

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

	BFS();
	
	int max = -1;
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (dis[i][j] > max)
				max = dis[i][j];			
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (tomato[i][j] == 0) {
				cout << "-1";
				return 0;
			}
		}
	}

	cout << max;
}