[c++] 토마토(BFS)

토마토(BFS)

#include <iostream>
#include <vector>
#include <stdlib.h>
#include <queue>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};
int k, m, n, res=-2147000000, map[1010][1010], dis[1010][1010];
struct Loc {
	int x;
	int y;
	Loc(int a, int b){
		x = a;
		y = b;		
	}
};
queue<Loc> Q;
int main() {
	//freopen("input.txt", "rt", stdin);
	scanf("%d %d", &m, &n);
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			scanf("%d", &map[i][j]);
			if(map[i][j]==1){
				Q.push(Loc(i, j));
			}
		}
	}
	while(!Q.empty()){
		Loc loc =Q.front();
		Q.pop();
		for(k=0; k<4; k++){
			int xx = loc.x + dx[k];
			int yy = loc.y + dy[k];
			if(map[xx][yy]==0 && xx<=n && xx>=1 && yy<=m && yy>=1){
				Q.push(Loc(xx, yy));
				map[xx][yy]=1;
				dis[xx][yy]=dis[loc.x][loc.y]+1;
			}
		}
	}
	int f=1;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			if(map[i][j]==0) f=0;
		}
	}
	if(f==1){
		for(int i=1; i<=n; i++){
			for(int j=1; j<=m; j++){
				if(res<dis[i][j]) res=dis[i][j];
			}
		}
		printf("%d\n", res);
	}
	else printf("-1");
	return 0;
}

넓이우선탐색문제이다. 

map을 입력받으면서 1이면 큐에 push한다. push된 값들을 하나씩 꺼내면서 큐에 깂이 남아있지 않을 때까지 

값들을 꺼내면서 1로 체크하고 큐에 push한다.

동시에 dis배열의 체크한 좌표에 지금까지의 값에 1을 더한다.

이렇게 큐에 남는값이 없을 때까지 반복해서 dis배열에 값을 넣어준다.

 

만약 이러한 과정이 끝났는데도 0이 남아있다면 그것은 토마토가 모두 익지 못하는 상황이므로 -1을 출력해주고

0이 남아있지 않다면 dis배열을 돌면서 가장 큰 값을 찾아서 프린트한다.