[백준] 2573번 빙산 (java, 시뮬레이션, bfs)

www.acmicpc.net/problem/2573

2573번: 빙산

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

class Pos{
	int y,x;

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

public class Main {
	static int n,m;
	static int[][] map;
	static int[] xpos= {0,0,1,-1};
	static int[] ypos= {1,-1,0,0};
	static boolean[][] vis;
	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;
		while(true) {
			if(isDone())break;
			melt();
			time++;
		}
		System.out.println(time);
		
	}
	private static boolean isDone() {
		vis=new boolean[n][m];
		int cnt=0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if(vis[i][j]==false && map[i][j]!=0) {
					if(cnt==1)return true;//두 덩이 이상으로 분리됨
					Queue<Pos> q=new LinkedList<Pos>();
					q.add(new Pos(i,j));
					vis[i][j]=true;
					while(q.size()!=0) {
						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(yy<0 || xx<0 || xx>=m || yy>=n)continue;
							if(vis[yy][xx])continue;
							if(map[yy][xx]>0) {
								q.add(new Pos(yy,xx));
								vis[yy][xx]=true;
							}
						}
					}
					cnt++;
				}
			}
		}
		if(cnt==0) {// 다 녹을때까지 분리 안됨
			System.out.println(0);
			System.exit(0);
		}
		return false;
	}
	private static void melt() {
		int[][] copy=new int[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if(map[i][j]!=0) {
					for (int k = 0; k < 4; k++) {
						int yy=i+ypos[k];
						int xx=j+xpos[k];
						if(yy<0 || xx<0 || xx>=m || yy>=n)continue;
						if(map[yy][xx]==0) {//주변의 0의 개수를 세준다.
							copy[i][j]+=1;
						}
					}
					
				}
			}
		}
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if(map[i][j]!=0) {
					if(copy[i][j]>=map[i][j]) {//만약 주변 물개수>빙하크기
						map[i][j]=0;
					}else {
						map[i][j]-=copy[i][j];// 아직 빙하가 더 크다
					}
				}
			}
		}
		
	}
	
	
}