[백준 7576] 토마토(2차원)

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

문제설명

1. 2차원 배열의 토마토 농장을 준다.(최대 1,000*1,000)
2. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.
3. 익은 토마토는 다음날 상하좌우 토마토를 익게 만든다.
4. 여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

bfs

옛날에 문제해결기법 수업을 들을 때 비슷한 문제가 있었다(당시엔 세균 감염?인가로 나왔다.)
그 때 상하좌우 di, dj 배열을 만들어 for문을 도는 풀이를 공유한 학우가 고맙게도 있었다.

코드

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

int arr[1000][1000];
struct pos {
	int a, b;
	pos(int aa, int bb) {
		a = aa; b = bb;
	}
};
int da[] = { 1,-1,0,0 };
int db[] = { 0,0,1,-1 };


int main() {
	int m, n;
	cin >> m >> n;
	int tomato;
	queue<pos> q;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> tomato;
			arr[i][j] = tomato;
			if (tomato == 1) {
				q.push(pos(i, j));
			}
		}
	}



	while (!q.empty()) {
		pos curpos = q.front();
		q.pop();
		//check adjacency
		for (int i = 0; i < 4; i++) {
			int childa = curpos.a + da[i];
			int childb = curpos.b + db[i];
			if (childa >= 0 && childb >= 0 && childa < n&&childb < m&&arr[childa][childb] == 0) {
				//범위를 넘지 않고 안 익은 토마토에 대해서만
				q.push(pos(childa, childb));
				arr[childa][childb] = arr[curpos.a][curpos.b] + 1;
			}

		}
		
	}

	/*
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << arr[i][j] << " ";
		}
		cout << endl;
	}
	*/


	bool has0 = false;
	int maxdate = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (maxdate < arr[i][j]) {
				maxdate = arr[i][j];
			}
			if (arr[i][j] == 0) {
				has0 = true;
			}
		}
	}
	if (!has0) {
		cout << maxdate-1<< endl;
	}
	else if (has0) {
		cout << -1 << endl;
	}

}