문제
M×N 격자 상자에 토마토가 들어있다. 익은 토마토(1)의 인접한 익지 않은 토마토(0)는 하루가 지나면 익는다. 모든 토마토가 익는 최소 일수를 구하는 문제다. 모두 익을 수 없으면 -1을 출력한다.
처음 익은 토마토가 하나라면 그 칸에서 BFS를 시작하면 된다. 이 문제에서는 익은 토마토가 여러 칸일 수 있다. 어느 하나를 먼저 처리하면 다른 토마토가 동시에 퍼뜨리는 하루를 표현할 수 없으므로, 처음부터 익어 있는 모든 칸을 같은 시각의 시작점으로 큐에 넣어야 한다. 이것이 다중 시작점 BFS다.
예를 들어 두 익은 토마토 사이에 익지 않은 칸이 있다면, 그 칸은 가까운 쪽에서 먼저 도달한 날짜에 익는다. BFS가 처음 기록한 날짜가 곧 최소 날짜가 되는 이유다.
핵심 포인트
- 다중 시작점 BFS: 익은 토마토가 여러 개일 수 있다. 모든 익은 토마토를 큐에 먼저 넣고 BFS를 시작한다.
- 동시 전파: 하루에 모든 익은 토마토가 동시에 영향을 미친다. BFS의 레벨 단위 탐색이 이를 자연스럽게 구현한다.
- 종료 판정: BFS가 끝난 후 아직 0인 칸이 남아있으면 -1이다.
C++ 풀이
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct Point { int y, x; };
int box[1000][1000];
int height, width;
queue<Point> q;
const int dy[4] = {-1, 1, 0, 0};
const int dx[4] = {0, 0, -1, 1};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> width >> height;
for (int y = 0; y < height; ++y) {
for (int x = 0; x < width; ++x) {
cin >> box[y][x];
if (box[y][x] == 1) q.push({y, x});
}
}
while (!q.empty()) {
Point current = q.front();
q.pop();
for (int dir = 0; dir < 4; ++dir) {
int ny = current.y + dy[dir];
int nx = current.x + dx[dir];
if (ny < 0 || ny >= height || nx < 0 || nx >= width) continue;
if (box[ny][nx] != 0) continue;
// 1이 첫날이므로 다음 칸에는 현재 값 + 1을 기록한다.
box[ny][nx] = box[current.y][current.x] + 1;
q.push({ny, nx});
}
}
int lastDay = 1;
for (int y = 0; y < height; ++y) {
for (int x = 0; x < width; ++x) {
if (box[y][x] == 0) {
cout << -1;
return 0;
}
lastDay = max(lastDay, box[y][x]);
}
}
cout << lastDay - 1;
return 0;
}
풀이 흐름
- 입력을 받으면서 익은 토마토(1)를 모두 큐에 넣는다. 이것이 다중 시작점 BFS의 핵심이다.
- 익지 않은 칸을 처음 발견하면 현재 칸의 날짜에 1을 더해 저장한다. 큐에 넣는 순간 값을 바꾸므로 같은 칸이 중복으로 들어가지 않는다.
- BFS가 끝난 뒤 0이 남아 있으면 도달할 수 없는 토마토이므로 -1이다.
- 1을 시작일로 사용했으므로 상자에 남은 최댓값에서 1을 뺀 값이 실제 경과 일수다.
주의사항
단일 시작점 BFS와의 차이: 일반 BFS 문제는 시작점이 하나지만, 이 문제는 시작점이 여러 개다. “처음에 모든 시작점을 큐에 넣는다”는 패턴을 기억해두면 불 번지기, 바이러스 전파 같은 유사 문제에 바로 적용할 수 있다.
복잡도
- 시간: O(N × M) — 모든 칸을 한 번씩 방문
- 공간: O(N × M) — 맵 배열 + 방문 배열
모든 익은 토마토에서 동시에 BFS를 시작하면, 각 칸에 최초로 도달하는 시점이 곧 그 칸의 토마토가 익는 최소 일수가 된다.
댓글