NรM (5โคN, Mโค100)์ ๋ชจ๋์ข ์ด ์์ ์์ฃผ ์์ ์น์ฆ๊ฐ <๊ทธ๋ฆผ 1>๊ณผ ๊ฐ์ด ํ์๋์ด ์๋ค. ๋จ, N ์ ์ธ๋ก ๊ฒฉ์์ ์์ด๊ณ , M ์ ๊ฐ๋ก ๊ฒฉ์์ ์์ด๋ค. ์ด ์น์ฆ๋ ๋๋ ๋ณด๊ด์ ํด์ผ๋ง ํ๋๋ฐ ์ค๋ด์จ๋์ ๋ด์ด๋์ผ๋ฉด ๊ณต๊ธฐ์ ์ ์ดํ์ฌ ์ฒ์ฒํ ๋ น๋๋ค. ๊ทธ๋ฐ๋ฐ ์ด๋ฌํ ๋ชจ๋์ข ์ด ๋ชจ์์ ์น์ฆ์์ ๊ฐ ์น์ฆ ๊ฒฉ์(์ ์ ์ ์ฌ๊ฐํ ๋ชจ์)์ 4๋ณ ์ค์์ ์ ์ด๋ 2๋ณ ์ด์์ด ์ค๋ด์จ๋์ ๊ณต๊ธฐ์ ์ ์ดํ ๊ฒ์ ์ ํํ ํ์๊ฐ๋ง์ ๋ น์ ์์ด์ ธ ๋ฒ๋ฆฐ๋ค. ๋ฐ๋ผ์ ์๋ <๊ทธ๋ฆผ 1> ๋ชจ์๊ณผ ๊ฐ์ ์น์ฆ(ํ์์ผ๋ก ํ์๋ ๋ถ๋ถ)๋ผ๋ฉด C๋ก ํ์๋ ๋ชจ๋ ์น์ฆ ๊ฒฉ์๋ ํ ์๊ฐ ํ์ ์ฌ๋ผ์ง๋ค.
<๊ทธ๋ฆผ 2>์ ๊ฐ์ด ์น์ฆ ๋ด๋ถ์ ์๋ ๊ณต๊ฐ์ ์น์ฆ ์ธ๋ถ ๊ณต๊ธฐ์ ์ ์ดํ์ง ์๋ ๊ฒ์ผ๋ก ๊ฐ์ ํ๋ค. ๊ทธ๋ฌ๋ฏ ๋ก ์ด ๊ณต๊ฐ์ ์ ์ดํ ์น์ฆ ๊ฒฉ์๋ ๋ น์ง ์๊ณ C๋ก ํ์๋ ์น์ฆ ๊ฒฉ์๋ง ์ฌ๋ผ์ง๋ค. ๊ทธ๋ฌ๋ ํ ์๊ฐ ํ, ์ด ๊ณต๊ฐ์ผ๋ก ์ธ๋ถ๊ณต๊ธฐ๊ฐ ์ ์ ๋๋ฉด <๊ทธ๋ฆผ 3>์์์ ๊ฐ์ด C๋ก ํ์๋ ์น์ฆ ๊ฒฉ์๋ค์ด ์ฌ๋ผ์ง๊ฒ ๋๋ค.
๋ชจ๋์ข ์ด์ ๋งจ ๊ฐ์ฅ์๋ฆฌ์๋ ์น์ฆ๊ฐ ๋์ด์ง ์๋ ๊ฒ์ผ๋ก ๊ฐ์ ํ๋ค. ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง ์น์ฆ๊ฐ ๋ชจ๋ ๋ น์ ์์ด์ง๋๋ฐ ๊ฑธ๋ฆฌ๋ ์ ํํ ์๊ฐ์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์๋ ๋ชจ๋์ข ์ด์ ํฌ๊ธฐ๋ฅผ ๋ํ๋ด๋ ๋ ๊ฐ์ ์ ์ N, M (5โคN, Mโค100)์ด ์ฃผ์ด์ง๋ค. ๊ทธ ๋ค์ N๊ฐ์ ์ค์๋ ๋ชจ๋์ข ์ด ์์ ๊ฒฉ์์ ์น์ฆ๊ฐ ์๋ ๋ถ๋ถ์ 1๋ก ํ์๋๊ณ , ์น์ฆ๊ฐ ์๋ ๋ถ๋ถ์ 0์ผ๋ก ํ์๋๋ค. ๋ํ, ๊ฐ 0๊ณผ 1์ ํ๋์ ๊ณต๋ฐฑ์ผ๋ก ๋ถ๋ฆฌ๋์ด ์๋ค.
์ถ๋ ฅ
์ถ๋ ฅ์ผ๋ก๋ ์ฃผ์ด์ง ์น์ฆ๊ฐ ๋ชจ๋ ๋ น์ ์์ด์ง๋๋ฐ ๊ฑธ๋ฆฌ๋ ์ ํํ ์๊ฐ์ ์ ์๋ก ์ฒซ ์ค์ ์ถ๋ ฅํ๋ค.
๐ก ์น์ฆ(1), ์ด๊ธฐ ๊ณต๊ธฐ(0), ์ธ๋ถ ๊ณต๊ธฐ(9)
๐ก 0. ์น์ฆ ์๋์ง ์ฌ๋ถ ํ์
map์ ์น์ฆ(1)๊ฐ ํ๋๋ผ๋ ์์ผ๋ฉด return false
์๋๋ผ๋ฉด, return true
๐ก 1. ์ธ๋ถ ๊ณต๊ธฐ, ๋ด๋ถ ๊ณต๊ธฐ ๊ตฌ๋ณ
BFS ์ธ๋ถ๊ณต๊ธฐ(9)๋ (0,0)์์ ์์๋์ด์ ๋ชจ๋ ์ฐ๊ฒฐ๋์ด ์์
๐ก 2. ์น์ฆ ๋
น์ด๊ธฐ
์น์ฆ(1)๋ฅผ ์ฐพ๊ณ 4๋ณ ์ค 2๋ณ์ด ์ธ๋ถ๊ณต๊ธฐ(9)์ด๋ฉด, ์น์ฆ(1)๋ฅผ ์ด๊ธฐ๊ณต๊ธฐ(0)๋ก
๋ฐ๊ฟ
๐ก 3. ์ด๊ธฐํ
์น์ฆ๊ฐ ๋
น๊ณ ๋ ํ, ์ธ๋ถ ๊ณต๊ธฐ์ ๋ด๋ถ ๊ณต๊ธฐ๋ฅผ ๊ตฌ๋ถํ๊ธฐ ์ํด, ์ธ๋ถ ๊ณต๊ธฐ
(9)๋ฅผ ๋ชจ๋ ์ด๊ธฐ ๊ณต๊ธฐ(0)๋ก ๋ฐ๊ฟ
๐ก 0-3๊น์ง 0์ด true๊ฐ ๋์ฌ ๋๊น์ง ๋ฐ๋ณตํจ
static boolean check() {
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if(map[i][j] == 1)
return false;
}
}
return true;
}
static void OutsideAir() {
Queue<Node> q = new LinkedList<>();
q.add(new Node(0,0));
visited[0][0] = true;
map[0][0] = 9;
while(!q.isEmpty()) {
Node now = q.poll();
for(int i=0; i<4; i++) {
int nx = now.x + dx[i];
int ny = now.y + dy[i];
if(nx < 0 || ny<0 || nx>=n || ny>=m)
continue;
if(map[nx][ny] == 0 && visited[nx][ny] == false) {
map[nx][ny] = 9;
visited[nx][ny] = true;
q.add(new Node(nx,ny));
}
}
}
}
static void meltCheese() {
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
int count = 0;
if(map[i][j] == 1) {
for(int k=0; k<4; k++) {
int nx = i + dx[k];
int ny = j + dy[k];
if(nx < 0 || ny < 0 || nx>=n || ny>=m)
continue;
if(map[nx][ny] == 9)
count++;
}
if(count >= 2) map[i][j] = 0;
}
}
}
}
static void init() {
map[0][0] = 0;
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if(map[i][j] == 9)
map[i][j] = 0;
visited[i][j] = false;
}
}
}
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Queue;
import java.util.LinkedList;
public class Bruteforce_3 {
static int[][] map;
static boolean[][] visited;
static int[] dx = {0,0,1,-1};
static int[] dy = {1,-1,0,0};
static int n, m;
static Queue<Node> entireQ = new LinkedList<>();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().split(" ");
int time = 0;
n = Integer.parseInt(s[0]);
m = Integer.parseInt(s[1]);
map = new int[n][m];
visited = new boolean[n][m];
for(int i=0; i<n; i++) {
s = br.readLine().split(" ");
for(int j=0; j<m; j++) {
map[i][j] = Integer.parseInt(s[j]);
}
}
while(true) {
if(check())
break;
OutsideAir();
meltCheese();
init();
time++;
}
System.out.println(time);
}
static void OutsideAir() {
Queue<Node> q = new LinkedList<>();
q.add(new Node(0,0));
visited[0][0] = true;
map[0][0] = 9;
while(!q.isEmpty()) {
Node now = q.poll();
for(int i=0; i<4; i++) {
int nx = now.x + dx[i];
int ny = now.y + dy[i];
if(nx < 0 || ny<0 || nx>=n || ny>=m)
continue;
if(map[nx][ny] == 0 && visited[nx][ny] == false) {
map[nx][ny] = 9;
visited[nx][ny] = true;
q.add(new Node(nx,ny));
}
}
}
}
static void meltCheese() {
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
int count = 0;
if(map[i][j] == 1) {
for(int k=0; k<4; k++) {
int nx = i + dx[k];
int ny = j + dy[k];
if(nx < 0 || ny < 0 || nx>=n || ny>=m)
continue;
if(map[nx][ny] == 9)
count++;
}
if(count >= 2) map[i][j] = 0;
}
}
}
}
static boolean check() {
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if(map[i][j] == 1)
return false;
}
}
return true;
}
static void init() {
map[0][0] = 0;
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if(map[i][j] == 9)
map[i][j] = 0;
visited[i][j] = false;
}
}
}
static class Node{
int x;
int y;
Node(int x, int y){
this.x = x;
this.y = y;
}
}
}
์ฑ๊ณตโจ