백준 7576 토마토 //bfs 레벨(깊이) 구별하는법

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

7576번: 토마토

 

1. 입력받다가 토마토(1)들이 있으면 좌표를 큐에 넣기 => 초기 트리 생성됨.(level 0)

※ bfs 레벨 구별법

1.초기값 qSize저장

2.qSize만큼 탐색하기

ex) Q : 2,1 -> 이면

2회만큼 돌고

2,1은 팝되고

그 이후 level이 ++됨. 

int level=0;
		
while(!q.isEmpty())
{
    //이렇게 해야 레벨(깊이)별로 구별 가능!!!!
    int qSize=q.size();
    for(int i=0;i<qSize;i++)
    {
        int[] parent = q.poll();

        //인접영역 탐색
        play(parent[0],parent[1]);
        //print();
        //System.out.println("================");
    }

    level++;

3. level별로 탐색하면서

4. 부모하나를 꺼냄

5. 그 부모의 인접자식에 대해 play(맵을 1로 바꿈), 큐에 추가

6. 한 레벨이 끝났다 == 하루가 지났다. -> answer++

참고 : 초반부터 answer이 +1 됨(-) -> 정답에 -1 해주면 됨.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_7576_유동훈 {

	static int N;
	static int M;
	static int[][] map;
	static Queue<int[]> q = new LinkedList<>();
	static int answer;
	
	static void print()
	{
		for(int i=0;i<N;++i)
		{
			//st=new StringTokenizer(br.readLine());
			for(int j=0;j<M;++j)
			{
				System.out.print(map[i][j]);
			}
			System.out.println();
		}
	}
	
	static void bfs()
	{
		//큐에 토마토(x,y) 저장
		
		//int[] parent=q.peek();
		int level=0;
		
		while(!q.isEmpty())
		{
			//이렇게 해야 레벨(깊이)별로 구별 가능!!!!
			int qSize=q.size();
			for(int i=0;i<qSize;i++)
			{
				int[] parent = q.poll();
				
				//인접영역 탐색
				play(parent[0],parent[1]);
				//print();
				//System.out.println("================");
			}

			level++;
			answer++;
			
		}
		
	}
	
	//상,하,좌,우 1로 만들기
	//상,하,좌,우 자식 추가
	static void play(int r, int c)
	{
		
		if(r-1>=0 && map[r-1][c]==0)
		{
			map[r-1][c]=1;
			q.add(new int[] {r-1,c});

		}
		if(r+1<N && map[r+1][c]==0)
		{
			map[r+1][c]=1;
			q.add(new int[] {r+1,c});

		}
		if(c-1>=0 && map[r][c-1]==0)
		{
			map[r][c-1]=1;
			q.add(new int[] {r,c-1});

		}
		if(c+1<M && map[r][c+1]==0)
		{
			map[r][c+1]=1;
			q.add(new int[] {r,c+1});

		}

		
	}
	
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st;
		st=new StringTokenizer(br.readLine());
		M=Integer.parseInt(st.nextToken());
		N=Integer.parseInt(st.nextToken());
		
		map=new int[N][M];
		for(int i=0;i<N;++i)
		{
			st=new StringTokenizer(br.readLine());
			for(int j=0;j<M;++j)
			{
				map[i][j]=Integer.parseInt(st.nextToken());
				if(map[i][j]==1) q.add(new int[] {i,j});
			}
		}
		
		bfs();
		//print();
		
		//맵에 0이 남아있음->불가능->-1
		for(int i=0;i<N;++i)
		{
			//st=new StringTokenizer(br.readLine());
			for(int j=0;j<M;++j)
			{
				//map[i][j]=Integer.parseInt(st.nextToken());
				if(map[i][j]==0)
				{
					System.out.println(-1);
					System.exit(0);
				}
			}
		}
		
		
		//System.out.println();
		System.out.println(answer-1);
		

	}


}