[C/C++ 백준 7576번] 토마토 (Silver 1)

www.acmicpc.net/problem/7576

7576번: 토마토

1에서 0으로 1이 점점 퍼져 나가는 모양새가 나오도록 코드를 짜야한다. 당연히 bfs를 사용하고, 각 bfs의 단계를 따지기 위해 depth 배열도 만들어 사용한다.

 

기본적으로 배열을 모두 받아놓은 뒤, 그래프의 모든 1에서 bfs과정을 수행하며 queue에 넣어준다. 이후 과정은 기존 bfs과정과 같은데, 모든 과정이 끝난후 0이 남아있다면 -1을 출력하고, 아니라면 depth값중 가장 큰 값을 출력한다.

 

//각 그래프들이 연결되어있는지의 여부
//연결되어 있지 않을 경우 1이 들어있는지여부
//1이 없음 -1, 모두 있으면 제대로 진행 
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
int M, N, maxi = -1;
int graph[1002][1002];
int depth[1002][1002];
bool visit[1002][1002];
int xmove[4]={-1,1,0,0};
int ymove[4]={0,0,1,-1};
typedef struct point{
	int x;
	int y;
}point;
void bfs(){
	queue <point> q;
	for(int i=1; i<=N; i++){
		for(int j=1; j<=M; j++){
			if(graph[i][j]==1){
				point a; a.x = i; a.y = j;
				q.push(a);
			}
		}
	}
	while(!q.empty()){
		point temp = q.front();
		q.pop();
		for(int i=0; i<4; i++){
			if(graph[temp.x+xmove[i]][temp.y+ymove[i]] == 0 ){
				graph[temp.x+xmove[i]][temp.y+ymove[i]] = 1;
				point tmp;
				tmp.x = temp.x+xmove[i];
				tmp.y = temp.y+ymove[i];
				depth[tmp.x][tmp.y] = depth[temp.x][temp.y] + 1;
				q.push(tmp);
			}
		}
	}
}
int main(void){	
	memset(depth, 0, 1001*1001*sizeof(int));
	scanf("%d %d", &M, &N);
	for(int i=0; i<=N+1; i++){
		graph[i][0] = -1;
		graph[i][M+1] = -1;
	}
	for(int i=0; i<=M+1; i++){
		graph[0][i] = -1;
		graph[N+1][i] = -1;
	}
	for(int i=1; i<=N; i++){
		for(int j=1; j<=M; j++){
			visit[i][j]=false;
			scanf(" %d", &graph[i][j]);
			if(graph[i][j]==1)
				depth[i][j] = 1;
		}
	}
	bfs();
	bool success=true;
	for(int i=1; i<=N; i++){
		for(int j=1; j<=M; j++){
			if(graph[i][j] == 0)
				success = false;
			maxi = max(maxi, depth[i][j]);
		}
	}
	if(!success)
		printf("-1");
	else
		printf("%d", maxi-1);
}