백준 7576 - 토마토

문제 

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

7576번: 토마토

풀이

1. 큐에 익은 토마토 좌표와 시간을 넣고, 재방문하지 않기위해 visited를 1로 넣는다.  (main 함수)

2. 익은 토마토 주변 토마토를 방문하지 않았으면 안익은 토마토를 큐에넣으면서 순회한다. (bfs 함수)

3. 큐가 비었는데 안익은 안익은 토마토가 있으면 -1을 반환하고 다 익었으면 시간을 반환한다 (check함수)

#include<iostream>
#include<cstring>
#include<queue>

using namespace std;

int N, M;
int map[1001][1001];
int visited[1001][1001];
int ans;
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0, 1,-1 };

struct dd {
	int _x, _y, _num;
	dd(int x, int y, int num) { _x = x; _y = y; _num = num; }
};

queue<dd> q;
void bfs() {
	while (!q.empty()) {
		int cx = q.front()._x;
		int cy = q.front()._y;
		int cnum = q.front()._num;
		q.pop();
		map[cx][cy] = cnum;
		bool push = false;
		for (int d = 0; d < 4; d++) {
			int nx = cx + dx[d];
			int ny = cy + dy[d];
			if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
			if (!visited[nx][ny] && map[nx][ny] == 0) {
				visited[nx][ny] = 1;
				dd nd = dd(nx, ny, cnum + 1);
				q.push(nd);
			}
		}
	}
}

int check() {
	//printf("\n\n");
	int max = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			//printf("%d ", map[i][j]);
			if (map[i][j] == 0) {
				return -1;
			}
			else if (map[i][j] > max) {
				max = map[i][j];
			}
		}
		//printf("\n");
	}
	return max - 1;
}
int main() {
	cin >> M >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (visited[i][j] == 0 && map[i][j] == 1) {
				visited[i][j] = 1;
				dd d = dd(i, j, 1);
				q.push(d);
			}
		}
	}
	bfs();
	cout << check();
	return 0;
}