[백준] 2636. 치즈 (bfs, java)

공기랑 닿는 부분 (처음 0,0 좌표에서 시작해서 0인 부분(처음 공기인 부분)과 -1(치즈가 녹아 공기가 된 부분)을 공기로 체크해준다. (공기: -1)

 

공기와 만나는 치즈는 녹을 치즈(2)로 만들어준다.

 

2의 개수를 세고 치즈를 모두 녹여준다(-1로 만들어줌)

 

만약 1인 치즈가 있으면 반복한다.

import java.util.Arrays;
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_2636_치즈_Main {
	static int n,m;
	static int[][] map;
	static boolean vis[][];
	static int xpos[]= {0,0,1,-1};
	static int ypos[]= {1,-1,0,0};
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		map=new int[n][m];
		vis=new boolean[n][m];
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <m; j++) {
				map[i][j]=sc.nextInt();
			}
		}
		int time=0;
		int answer=0;
		while(true) {
			if(isEmpty()) {
				break;
			}
			for (int i = 0; i < n; i++) {
				Arrays.fill(vis[i], false);
			}
			check();
			for (int i = 0; i < n; i++) {
				Arrays.fill(vis[i], false);
			}
			answer=melt();
			time++;
		}
		System.out.println(time);
		System.out.println(answer);
	}

	private static int melt() {
		int cnt=0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <m; j++) {
				if(map[i][j]==2) {
					map[i][j]=-1;//녹아서 공기가 된 치즈
					cnt+=1;
				}
			}
		}
		return cnt;
	}

	private static void check() {
		Queue<Pos> q=new LinkedList<Pos>();
		q.add(new Pos(0,0));
		vis[0][0]=true;
		map[0][0]=-1;//공기
		while(q.size()!=0) {
			Pos cur=q.poll();
			int y=cur.y;
			int x=cur.x;
			for (int i = 0; i < 4; i++) {
				int yy=y+ypos[i];
				int xx=x+xpos[i];
				if(xx<0 || yy<0 || xx>=m || yy>=n)continue;
				if(vis[yy][xx])continue;
				if(map[yy][xx]==0 || map[yy][xx]==-1) { //이미 공기인 부분과 새로 녹은 부분 모두 공기
					vis[yy][xx]=true;
					q.add(new Pos(yy,xx));
				}else {
					map[yy][xx]=2; //녹을 치즈 부분
				}
			}
		}
		
	}

	private static boolean isEmpty() {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <m; j++) {
				if(map[i][j]==1)return false;
			}
		}
		return true;
	}
}