[백준] 7576번 토마토 (bfs)

www.acmicpc.net/problem/7576

7576번: 토마토

 

한 번에 1인 곳 주변이 모두 익어야되기 때문에 큐에 현재 1인곳을 다 집어넣고 

매번 순회할 시에 모두 bfs탐색을 한꺼번에 해준다.

 

for문 (현재 익어있는 토마토 개수)만큼 bfs를 돌면서 큐에 넣어준 다음에야 다음 차례의 토마토들이 

큐에서 나온다.

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Pos{
	int y;
	int x;
	public Pos(int y, int x) {
		super();
		this.y = y;
		this.x = x;
	}
	
}

public class B_7576_토마토_Main {
	static int m,n;
	static int[][] map;
	static int[] xpos= {1,-1,0,0};
	static int[] ypos= {0,0,1,-1};
	static Queue<Pos> q=new LinkedList<Pos>();
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		m=sc.nextInt();
		n=sc.nextInt();
		map=new int[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				map[i][j]=sc.nextInt();
				if(map[i][j]==1)q.add(new Pos(i,j));
			} 
		}
		int time=0;
		while(q.size()!=0) {
			int len=q.size();
			
			for (int i = 0; i < len; i++) {
				Pos cur=q.poll();
				int y=cur.y;
				int x=cur.x;
				
				for (int k = 0; k < 4; k++) {
					int yy=y+ypos[k];
					int xx=x+xpos[k];
					if(xx<0 || yy<0 || xx>=m || yy>=n)continue;
					if(map[yy][xx]==1 || map[yy][xx]==-1)continue;
					map[yy][xx]=1;
					q.add(new Pos(yy,xx));
				}
			}
			if(q.size()!=0)time++;
		}
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if(map[i][j]==0) {
					time=-1;
					break;
				}
			}
		}
		System.out.println(time);
		
	}
}