[210327][백준/BOJ] 7576번 토마토

문제

입출력

풀이

상자 안에는 익은 토마토와 익지 않은 토마토가 존재한다. 익은 토마토는 하루가 지나면 상하좌우에 존재하는 익지 않은 토마토에 영향을 줘서 익은 상태가 된다.
상자에 익은 토마토와 익지 않은 토마토가 주어졌을때 모든 토마토가 익은 상태가 되는 최소 일수를 구하는 문제이다.

익은 토마토가 인접한 토마토들에게 영향을 주는 문제이므로 BFS를 통해 문제를 풀 수 있고 모든 토마토가 익은 상태가 되는 최소 일수는 거리를 구하는 방법을 이용해서 풀 수 있다.

이 문제는 시작점이 한개가 아니라 여러개 존재할 수 있으며 각 시작점이 동시에 실행 되어야 한다. 따라서

1. 일단 모든 시작점을 구해서 이를 큐에 넣어야 한다.
2. 거리를 구하기 위해 익지 않은 토마토의 거리값은 -1로 초기화를 한다.
3. 원소의 dist값이 0 이상인 경우에 continue로 한다면 이미 지나간 토마토나 토마토가 없는 칸도 한번에 처리할 수 있다.
4. 최소 일수를 구할 때 아직 익지 않은 토마토가 존재할 경우(dist[i][j] == -1)에는 -1을 출력해준다.

코드

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define SIZE 1002

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

// 거리 구하는 방식으로 최대 거리를 찾는다 
// 최대 거리가 최소 날짜가 됨

int main()
{
	int m, n; // m은 열, n은 행
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> m >> n;
	queue<pair<int, int>> Q;
	
	// 여러개의 시작점이 동시에 실행
	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 });
			if (board[i][j] == 0) // 익지않은 토마토라면
				dist[i][j] = -1; // -1로 초기화
		}
	}
	while (!Q.empty())
	{
		auto cur = Q.front(); Q.pop();
		for (int dir = 0; dir < 4; ++dir)
		{
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (dist[nx][ny] >= 0) continue; // 이미 지나간 토마토나 토마토가 없는 칸도 커버가능
			dist[nx][ny] = dist[cur.X][cur.Y] + 1;
			Q.push({ nx, ny });
		}
	}

	int mx = 0;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			if (dist[i][j] == -1) // 익지 않은 토마토가 있다면
			{
				cout << -1;
				return 0; // 프로그램 종료
			}
			mx = max(mx, dist[i][j]);
		}
	}
	cout << mx;
}