BOJ - 7576번_토마토

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램 작성하기

  • 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다.
  • 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.
  • 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.


풀이

모든 익은 토마토 시작점을 큐에 넣은 후 BFS를 시작한다. dist배열을 이용해 시작점과의 거리를 계산하고 익지 않은 토마토일 경우에는 -1을 넣는다.


소스코드

#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int board[1005][1005];
int dist[1005][1005];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int m, n;
	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; 
			}
		}
	}
	
	while(!q.empty()) {
		auto cur = q.front();
		q.pop();
		for(int k=0; k<4; k++) {
			int nx = cur.X + dx[k];
			int ny = cur.Y + dy[k];
			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 ans = 0;
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			if(dist[i][j]==-1) {
				cout << "-1";
				return 0;
			}
			ans = max(ans, dist[i][j]);
		}
	}
	cout << ans;
}