백준 7576 - 토마토

문제링크

• 백준 7576

문제설명

• N x M 크기의 창고가 있고, 1x1 크기의 상자들로 이루어져 있으며 각 상자에는 토마토를 보관한다.
• 각 상자에는 빈 칸(0), 잘 익은 토마토(1), 아직 익지 않은 토마토(2) 가 있을 수 있다.
• 보관 후 하루가 지나면 익은 토마토들의 상하좌우 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다.
• 창고에 보관된 토마토들이 며칠이 지나면 모두 익게 되는지 그 최소 일수를 구하라
• 모든 토마토가 익을 수 없다면 -1 을 출력하라

문제접근

• 시간초과로 풀지 못한 접근
  • 모든 익은 토마토의 좌표를 시작점으로 하여 창고 전체 영역으로 너비우선탐색을 한다.
  • 익는 동선이 겹치는 칸은 적게 소요된 날짜로 값을 갱신할 수 있도록 한다.
  • 최악의 경우 너비우선탐색을 백만번 반복해야 하고, 각각에 대해서 모든 정점을 방문해야 하고, 4가지 방향에 대해서 loop 를 형성하기 때문에 시간초과에 걸린다.
• 토마토가 아닌 날짜를 중심으로 문제 접근
  • 0일차, 1일차, 2일차 … 에 익은 토마토들의 좌표를 담는 인접리스트 vector<pair<int, int>> days[] 를 선언한다.
  • n일차 익은 토마토를 시작으로 인접한 칸에 방문하여 다음날에 익게 되는 토마토를 n+1 일차 배열에 담는다.
  • 토마토가 하나도 익지 않게 되는 날까지 위 과정을 반복한다.

구현

#include <iostream>
#include <vector>
#include <queue>
#define MAX 1000000
using namespace std;

int N, M;
int box[1000][1000];
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
// n일차에 익은 토마토의 좌표
vector<pair<int, int>> days[MAX];

int spendDay(int cday) {
	int nx, ny, cnt = 0;
	for (auto ele : days[cday]) {
		for (int dir = 0; dir < 4; dir++) {
			nx = ele.first + dx[dir];
			ny = ele.second + dy[dir];
			if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
			if (box[nx][ny] == 0) {
				box[nx][ny] = 1;
				days[cday + 1].push_back(make_pair(nx, ny));
				cnt++;
			}
		}
	}
	// 익은 토마토가 없다면 false 반환
	if (cnt == 0) return 0;
	return cday+1;
}

int tomatoProc() {
	int cday = 0, ret = 0, tmp = 0;
	while (true) {
		if ((tmp = spendDay(cday++)) == 0) break;
		ret = tmp;
	}

	// 익지 않은 토마토가 있다면 -1 반환
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < M; c++) {
			if (box[r][c] == 0) return -1;
		}
	}
	return ret;
}


int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	scanf("%d %d", &M, &N);

	int val = 0;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < M; c++) {
			scanf("%d", &val);
			box[r][c] = val;
			if (val == 1) days[0].push_back(make_pair(r, c));
		}
	}

	int ans = tomatoProc();
	printf("%d\n", ans);
	return 0;
}