백준 7576번: 토마토

[문제 링크]

7576번: 토마토

---

N,M의 최대값이 1000으로 꽤 큰편이기 때문에 그래프의 전체 탐색 횟수를 줄이기 위해 익은 토마토의 위치를 큐에 담아놓고 탐색하는 방법으로 구현하였다.

 

입력을 받을 때 안익은 토마토의 갯수를 카운팅하고 익은 토마토의 좌표를 큐에 담는다.

그 다음, 큐에 담긴 익은 토마토 좌표를 기준으로 동서남북을 확인하여 안익은 토마토를 찾아 해당 토마토를 익은 토마토로 바꾸고 큐에 담는다.

안익은 토마토의 갯수가 0이 되거나 새롭게 익은 토마토가 더이상 존재하지 않을 때까지 위 작업을 반복하면 된다.

 

안익은 토마토의 갯수가 0이 되었을때 반복한 횟수가 곧 최소 일수가 되며,

새롭게 익은 토마토가 더이상 존재하지 않을 때 안익은 토마토가 남아 있다면 토마토를 모두 익게 만드는 것은 불가능하다.

---

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

struct Pos {
	int y;
	int x;
};

// M: 가로, N: 세로
int M, N;
int adj[1000][1000];
int tomatoCnt;
int dy[4] = { 0,0,-1,1 };
int dx[4] = { 1,-1,0,0 };
queue<Pos> ripeTomatoQueue;

int getRipeTomatoDays() {
	int result = 0;

	while (tomatoCnt > 0) {
		if (ripeTomatoQueue.empty())
			return -1;

		result++;
		int qSize = ripeTomatoQueue.size();
		while (qSize--) {
			Pos herePos = ripeTomatoQueue.front();
			ripeTomatoQueue.pop();

			for (int i = 0; i < 4; i++) {
				Pos nextPos = { herePos.y + dy[i], herePos.x + dx[i] };
				
				if(nextPos.y >= 0 && nextPos.y < N && nextPos.x >= 0 && nextPos.x < M)
					if (adj[nextPos.y][nextPos.x] == 0) {
						adj[nextPos.y][nextPos.x] = 1;
						tomatoCnt--;
						ripeTomatoQueue.push(nextPos);
					}
			}
		}
	}

	return result;
}

int main(void) {
	cin.tie(0);

	cin >> M >> N;

	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			cin >> adj[y][x];
			Pos pos = { y,x };

			if (adj[y][x] == 0)
				tomatoCnt++;
			else if (adj[y][x] == 1)
				ripeTomatoQueue.push(pos);
		}
	}

	cout << getRipeTomatoDays() << endl;

	return 0;
}