[백준] 7576번 토마토 - C++

---

토마토

 위 그림과 같은 상자에 한 칸에 하나씩 토마토가 들어있고 익은 토마토는 하루 만에 인접한 토마토를 익게 만든다고 했을 때 모든 토마토가 익는데 걸리는 일수를 구하는 문제입니다.

---

입력

 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M, N ≤ 1,000이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

출력

 여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

예제 입력

6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

예제 출력

8

---

풀이방법

 처음에는 무작정 루프를 돌렸더니 시간초과가 떠서 중복을 줄이기 위해 bfs를 사용했습니다. 다만 bfs의 시작을 첫날부터 익어있는 모든 토마토로 넣어주고 day변수를 함께 bfs를 돌려서 며칠이 지났는지 알아낼 수 있도록 하였습니다.

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int m, n;
	cin >> m >> n;

	queue<pair<pair<int, int>, int>> bfs;
	vector<vector<int>> box(n, vector<int>(m));
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			cin >> box[i][j];
			if (box[i][j] == 1)
				bfs.push({ {i,j},0 });
		}
	}

	vector<pair<int, int>> dir = { {-1,0},{0,1},{1,0},{0,-1} };
	int day = 0;
	while (!bfs.empty())
	{
		int y = bfs.front().first.first;
		int x = bfs.front().first.second;
		day = bfs.front().second;
		bfs.pop();
		for (int i = 0; i < 4; ++i)
		{
			int ny = y + dir[i].first;
			int nx = x + dir[i].second;
			int nday = day + 1;
			if (ny < 0 || ny >= n || nx < 0 || nx >= m)
				continue;
			if (box[ny][nx] == 1 || box[ny][nx] == -1)
				continue;
			box[ny][nx] = 1;
			bfs.push({ {ny,nx},nday });
		}
	}

	bool isAllRed = true;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			if (box[i][j] == 0)
				isAllRed = false;
		}
	}
	if (isAllRed)
		cout << day;
	else
		cout << -1;

	return 0;
}

 

마치며

 두번째로 푼 골드문제!! 였지만 어제 해결했던 Z가 실버 1로 난이도 조정을 당하면서 다시 새로운 골드문제가 되었습니다. 첫 번째 골드문제를 푸는 경험을 두 번 하다니 럭키 한 날이네요.