[백준 7576 / C++] 토마토

bfs를 활용해서 풀면 되는 문제이다. 

지금까지 풀어왔던 bfs와는 조금 다른 점이 있었다. 

익은 토마토가 하나일 수도 있고 두개일 수도 있고 즉, 여러개일 수도 있다.  

다시말해, 여러 영역에서 익은 토마토들이 존재하면 동시에 움직이면서 visited를 세팅 해야한다는 것이다.  

주인공이 하나가 아니라는 뜻이다. 

 

익은 토마토들을 먼저 다 queue에 넣어줘서 bfs를 시작하게 된다. 

먼저 queue에 넣은 익은 토마토들의 x,y 좌표값을 vector에 넣어주고 

vector에 들어있는 각 좌표값의 상, 하, 좌, 우 를 모두 살펴보고 갈  수 있는 길이 있다면 그 값들을 모두 다시 큐에 넣어준다. 그러한 작업이 모두 이루어지고 나면 그때, cnt값을 하나 올려주는 것이다. 

#include <iostream>
#include <vector>
#include <tuple>
#include <queue>
using namespace std; 
int map[1000][1000]; 
int visited[1000][1000]; 
queue <pair<int, int>> q; 
int m, n;
int dx[4] = { 0,0,1,-1 }; 
int dy[4] = { 1,-1,0,0 }; 
int cnt = 0;
using namespace std;
void bfs() {
	int x, y; 
	while (!q.empty()) {
		vector <pair<int, int>>v; 
		while (!q.empty()) {
			tie(y, x) = q.front(); 
			q.pop(); 
			v.push_back({ y,x }); 
		}
		int check = 0; 
		for (int i = 0; i < v.size(); i++) {
			for (int j = 0; j < 4; j++) {
				int nx = dx[j] + v[i].second; 
				int ny = dy[j] + v[i].first; 
				if (nx<0 || nx>=n || ny<0 || ny>=m || map[ny][nx] == -1)continue; 
				if (visited[ny][nx] == 1)continue; 
				visited[ny][nx] = 1; 
				check = 1; 
				q.push({ ny,nx }); 
			}
		}
		if(check)cnt++; 
	}
}
int main() {
	cin >> n >> m; 
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j]; 
			if (map[i][j] == 1) {
				q.push({ i,j }); 
				visited[i][j] = 1; 

			}
			if (map[i][j] == -1)visited[i][j] = 1; 
		}
	}
	bfs(); 
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (visited[i][j] == 0) {
				cout << -1; 
				return 0; 
			}
		}
	}
	cout << cnt; 
}

7576번: 토마토