백준 7576(토마토) bfs

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

7576번: 토마토

딱 보고 bfs라고 생각이 든 문제. 

 

이 문제를 통해서 bfs와 dfs의 작동원리 차이점을 좀 더 이해할 수 있게 되었다. 

 

dfs는 한 번 가면 끝이 없다. 끝을 볼 때 까지 간다. (return 이 될때까지 돈다.)

bfs는 턴이라는 개념이 있다. 

 

주변을 다 돌고, 한 턴이 지나고, 다음 턴이 시작이다. 

 

문제에서 하루가 지나면 익은 토마토에 인접한 안 익은 토마토가 익는다고 했다. 

모두 다 익기 위해서 걸리는 시일을 구하려면

 

하루에 인접한 토마토들이 익는다는 사실을 중점으로 문제에 접근해야 했다.

 

만약 dfs로 풀려고 한다면 동시다발적으로 익는게 아니라서 며칠 걸릴지 구할 수가 없다. 

bfs는 인접한 모든 지점에 대해서 (하루에) 구하고, 다음 날 다시 조사를 하는 방식이다. 

 

따라서 queue를 두개 만들어서 queue1에 첫날에 익은거 집어넣고, queue2에 첫날에 익은걸로 인해서 익는 인접한 토마토의 index를 집어넣었다. 이걸 반복하면 모든 토마토가 하루하루 모두 익기 시작할 것이다. 

 

마지막으로 모든 토마토에 대해서 조사한 뒤 

아직 안 익은 토마토가 존재할 때, -1을 출력하는 코드로 짰다. 

 

#include<iostream>
#include<queue>
#include<utility>
using namespace std;
#define MAX 1001

queue<pair<int, int> > q1;
queue<pair<int, int> > q2;
pair<int, int> p;
int N, M, a, cnt=0;
int tomato[MAX][MAX];
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0,0,1,-1 };
bool check = false;
bool start = false;

void bfs() {
	while (!q1.empty() || !q2.empty()) {
		while (!q1.empty()) {
			p.first = q1.front().first;
			p.second = q1.front().second;
			q1.pop();
			for (int i = 0; i < 4; i++) {
				int x = p.second + dx[i];
				int y = p.first + dy[i];
				if (x < 0 || y < 0 || x >= M || y >= N) continue;
				if (tomato[y][x] == 0) {
					tomato[y][x] = 1;
					q2.push(make_pair(y, x));
				}
			}
			if (q1.empty()) {
				if(start)
					cnt++;
				else start = true;
			}
		}
		while (!q2.empty()) {
			p.first = q2.front().first;
			p.second = q2.front().second;
			q2.pop();
			for (int i = 0; i < 4; i++) {
				int x = p.second + dx[i];
				int y = p.first + dy[i];
				if (x < 0 || y < 0 || x >= M || y >= N) continue;
				if (tomato[y][x] == 0) {
					tomato[y][x] = 1;
					q1.push(make_pair(y, x));
				}
			}
			if (q2.empty()) cnt++;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> M >> N;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> a;
			tomato[i][j] = a;
			if (a == 1) {
				q1.push(make_pair(i, j));
			}
		}
	}
	bfs();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (tomato[i][j] == 0) check = true;
		}
	}
	if (check) {
		cout << -1 << "\n";
		return 0;
	}
	else {
		cout << cnt << "\n";
	}
}

check 변수로 처음에 괜히 하루를 계산하는 경우에 대해서 예외처리 해주었다.