백준 7576 토마토

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

 

아이디어

BFS를 풀이하는 일반적인 방식을 이용

 

1. 토마토 행렬을 배열에 입력하고, 토마토가 1이면 1인 토마토의 좌표를 큐에 푸시

 

2-0. 큐의 사이즈를 기억하고 큐에서 하나를 빼낸다. 빼낸 좌표가 (y,x)면

2-1. 빼낸 좌표의 (y,x+1) 값이 0이면 토마토를 1로 바꾸고 (y,x+1) 좌표를 큐에 푸시

2-2. 빼낸 좌표의 (y,x-1) 값이 0이면 토마토를 1로 바꾸고 (y,x-1) 좌표를 큐에 푸시

2-3. 빼낸 좌표의 (y+1,x) 값이 0이면 토마토를 1로 바꾸고 (y+1,x) 좌표를 큐에 푸시

2-4. 빼낸 좌표의 (y-1,x) 값이 0이면 토마토를 1로 바꾸고 (y-1,x) 좌표를 큐에 푸시

 

3. 2-0에서 기억한 큐의 사이즈만큼 2번 전체를 반복(계속 삽입되는 큐에서 이전 날짜에 익은 토마토만 빼내기 위해 큐의 사이즈를 기억시킨것)

 

4. 날짜+1

 

5. 큐가 비어있지 않다면 2번으로 이동

 

6. 토마토를 전수조사해서 0인 토마토가 있으면 -1 출력하고 없으면 날짜를 출력

 

---

구현

// c++

#include <iostream>
#include <queue>

using namespace std;

int m, n;
int box[1001][1001];
queue<pair<int, int>>q;

void input() {
	cin >> m >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int tmp;
			cin >> tmp;
			if (tmp == 1) {
				q.push(make_pair(i, j));
				box[i][j] = tmp;
			}
			else if (tmp == -1) box[i][j] = tmp;
		}
	}
}

int bfs() {
	int dy[4] = { -1,1,0,0 };
	int dx[4] = { 0,0,-1,1 };
	int result = -1;
	while (!q.empty()) {
		result++;
		int qSize = q.size();
		for (int i = 0; i < qSize; i++) {
			int y = q.front().first;
			int x = q.front().second;
			q.pop();
			for (int i = 0; i < 4; i++) {
				int yy = y + dy[i];
				int xx = x + dx[i];
				if (box[yy][xx] == 0 && yy>=0 && xx>=0 && yy<n && xx<m) { 
					q.push(make_pair(yy, xx)); 
					box[yy][xx] = 1;
				}
			}
		}
	}
	return result;
}

bool check() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (box[i][j] == 0) return false;
		}
	}
	return true;
}

int main() {
	int result = 0;
	input();
	result = bfs();
	if (check() == false) cout << -1;
	else cout << result;
}