[백준 7576/C++] 토마토

1. 문제

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

7576번: 토마토

---

2. 문제 풀이

#include <iostream>
#include <bits/stdc++.h>
#pragma warning (disable:4996)
#define X first
#define Y second

using namespace std;

int board[1002][1002];
int dist[1002][1002];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int ans;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, m;
	queue<pair<int, int>> Q;
	cin >> m >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> board[i][j];
			if (board[i][j] == 1) {
				Q.push({ i,j });
				dist[i][j] = 0;
			}
			else if (board[i][j] == 0)
				dist[i][j] = -1;
		}
	}
	while (!Q.empty()) {
		auto cur = Q.front(); Q.pop();
		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.first + dx[dir];
			int ny = cur.second + dy[dir];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (board[nx][ny] == -1 || dist[nx][ny] >= 0) continue;
			Q.push({ nx,ny });
			dist[nx][ny] = dist[cur.X][cur.Y] + 1;
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (dist[i][j] == -1) {
				cout << -1;
				return 0;
			}
			ans = max(ans, dist[i][j]);
		}
	}
	cout << ans;
}

---

3. 문제 평가 및 해설

BFS 문제에서 시작점이 여러개일 경우의 문제이다. 

처음 이 문제를 접했을 때, "Flood fill 알고리즘 처럼 NM을 순회하면서 시작 위치를 찾고 BFS를 돌리면 되지 않나?"라고 생각했다. 그런데 해당 풀이로 하면 BFS 시간 복잡도 O(NM)에 익은 토마토가 최대 NM개가 존재할 수 있기 때문에 O(N^2M^2)으로 시간 초과가 날 것이다. 그리고 첫번째 시작점에서 BFS를 수행하고 그 다음 시작점에서 BFS를 수행할 때 distance 배열을 또 처리해줘야하기 때문에, 너무 복잡할거라는 생각이 들었다.

그러나 복잡하게 생각하지 말고 간단하게 큐에 시작점을 여러개 넣어주면 된다. 

그런데도 값이 잘 안나오는 경우가 많은데, 문제에 꽤나 함정(?)이 많다. 밑의 경우를 처리해줬는데 살펴보면 좋을 것 같다.

1. int >> n >> m 이 아니라 int >> m >> n 이다. 대다수의 문제의 경우, 행->열 순으로 주는데 이 문제는 특이하게 열 행으로 줬다. 이 오류를 찾느라 한 세월이 걸렸다.

2. distance 배열을 처리하는 것을 잘 생각해야 한다. 무작정 -1로 모두 초기화하고 시작 위치를 0으로 초기하는 것이 아니라, 안익은 위치에만 -1로 처리해줘야 한다. 즉, 다시 말해 벽을 0으로 처리해야한다. 

2번 같은 경우, "그러면 모두 벽인 상황에선 -1로 출력되어야 하지 않느냐?"라고 생각할 수 있겠지만 문제 조건이 토마토가 최소 한 개 이상이라고 했으니 상관없는 case이다.