[C++] BOJ-7576

 

문제풀이

---

다른 BFS 문제와 마찬가지로 queue에 x좌표와 y좌표를 넣으면서 BFS를 돌리면 된다.

날짜가 지날때마다 토마토가 들어있지 않은 경우가 아니라면 인접한 배열을 1로 교체해주었다.

 

다른 BFS 문제와 다른점은 이 문제에서는 익지 않은 토마토가 있을 수 있기 때문에 그 경우까지 생각해줘야 한다.

 

나같은 경우 BFS로 모든 맵을 돌린 후 마지막에 map 배열에 0이 하나라도 존재한다면 -1을 return을 해주는 조건문을 하나 더 추가해주었다.

 

#include <iostream>
#include <queue>

using namespace std;

int dx[4] = {0,0,-1,1}; // 상하좌우 
int dy[4] = {1,-1,0,0};

int N,M;
int map[1001][1001];
int cnt;
queue< pair<int,int> > q;

int bfs(){
	while(!q.empty()){
		int x,y;
		x = q.front().first;
		y = q.front().second;
		
		q.pop();
		
		for(int i = 0; i<4; i++){
			int rx = x + dx[i];
			int ry = y + dy[i];
			
			
			if(rx >= 0 && ry >= 0 && rx < N && ry < M){
				
				if(map[rx][ry] == 0){
					map[rx][ry] = map[x][y] + 1;
					q.push(make_pair(rx,ry));
					cnt = map[rx][ry];
				}
			}
		}
	}
	
	for(int i = 0; i<N; i++){
		for(int j = 0; j<M; j++){
			if(map[i][j] == 0){
				return -1;
			}
		}
	}
	if(cnt == 0) return 0;
	return cnt-1;
}

int main(){
	cin >> M >> N;
	
	for(int i = 0; i<N; i++){
		for(int j = 0; j<M; j++){
			cin >> map[i][j];
			if(map[i][j] == 1){
				q.push(make_pair(i,j));
			}
		}
	}
	cout << bfs();
	
	return 0;
}