白準-2636号チーズ

方法

ソース

import java.util.*;
import java.io.*;

public class Main {
	static int N;
	static int M;
	static int TIME = 0;
	static int MASS = 0;
	static int[][] dir = {{-1,0},{1,0},{0,-1},{0,1}};
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		int[][] cheese = new int[N][M];
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < M; j++) {
				cheese[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		while(!checkZero(cheese)) {
			TIME++;
			cheese = bfs(cheese);
		}
		System.out.println(TIME);
		System.out.println(MASS);
	}
	static boolean checkZero(int[][] array) {
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if(array[i][j] != 0) return false;
			}
		}
		return true;
	}
	static int[][] bfs(int[][] array) {
		//깊은복사
		int[][] newArray = new int[N][M];
		int count = 0;
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				newArray[i][j] = array[i][j];
				if(array[i][j] == 1) count++;
			}
		}
				
		MASS = count;
		
		//치즈가 놓이지않는 0,0은 무조건 0이므로 이곳부터 bfs로 0인 항목을 모두 2로 바꿔줌
		boolean[][] visit = new boolean[N][M];
		Queue<Point2636> q = new LinkedList<Point2636>();
		
		visit[0][0] = true;
		q.offer(new Point2636(0,0));
		newArray[0][0] = 2;
		
		while(!q.isEmpty()) {
			Point2636 curP = q.poll();
			
			for(int i = 0; i < 4; i++) {
				int nextX = curP.x + dir[i][0];
				int nextY = curP.y + dir[i][1];
				
				//범위밖이면 패스
				if(nextX < 0 || nextX >= N || nextY < 0 || nextY >= M) continue;
				//방문을 안했고 0이면 변경대상
				if(!visit[nextX][nextY] && newArray[nextX][nextY] == 0) {
					visit[nextX][nextY] = true;
					q.offer(new Point2636(nextX, nextY));
					newArray[nextX][nextY] = 2;
				}				
			}
		}	
		
		/* 전체탐색으로 newArray가 2면 0으로(실제 0이니까)
		 * 1인데 주변에 2가 있으면 0으로 아니면 유지
		 * 0이면 0으로 유지
		 * 한 값을 새 retArray에 갱신하고 리턴
		 * 
		 */
		int[][] retArray = new int[N][M];
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if(newArray[i][j] == 0 || newArray[i][j] == 2) retArray[i][j] = 0;
				else if(newArray[i][j] == 1) {
					if(newArray[i-1][j] == 2 || newArray[i+1][j] == 2 || newArray[i][j-1] == 2 || newArray[i][j+1] == 2) {
						retArray[i][j] = 0;
					} else {
						retArray[i][j] = 1;
					}
				}
			}
		}
		return retArray;
	}
}

class Point2636{
	int x;
	int y;
	Point2636(int x, int y){
		this.x = x;
		this.y = y;
	}
}