[BOJ] 7576번 토마토 (C++)

https://www.acmicpc.net/problem/7576

7576번: 토마토

 

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

#define MAX 1001

int N, M;
int arr[MAX][MAX];
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };
queue <pair<int, int>> q;

void bfs() {
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx >= 0 && nx < M && ny >= 0 && ny < N && arr[nx][ny] == 0) {
				arr[nx][ny] = arr[x][y] + 1;
				q.push({nx, ny});
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int cnt = 0;
	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 1) {
				q.push({i, j});
			}
		}
	}
	
	
	bfs();
	
	
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			if (arr[i][j] == 0) {
				cout << -1 << endl; 
				return 0;
			}
			if(cnt < arr[i][j]) 
				cnt = arr[i][j];
		}
	}
	

	cout << cnt - 1 << endl;
	return 0;
}

지금까지 풀었던 bfs 문제들은 bfs 함수 내부에서 매개변수로 들어온 좌표들을 큐에 push 해주었지만 이 문제는 토마토 정보를 입력받을 때 익은 토마토의 좌표를 큐에 push한 뒤 queue에 담긴 익은 토마토들을 시작점으로 하여 bfs를 돌려야 한다.