-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path2573_๋น์ฐ.java
More file actions
99 lines (90 loc) ยท 3.56 KB
/
2573_๋น์ฐ.java
File metadata and controls
99 lines (90 loc) ยท 3.56 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.*;
public class Main {
static int N, M, time; //๊ฐ๋ก, ์ธ๋ก, ๊ฑธ๋ฆฐ์๊ฐ
static int[][] map;
static int[] dx = new int[] {-1,1,0,0}; //๋ฐฉํฅ๋ฒกํฐ
static int[] dy = new int[] {0,0,-1,1}; //๋ฐฉํฅ๋ฒกํฐ
static ArrayList<int[]> iceList; //๋น์ฐ ์์น ๋ฆฌ์คํธ
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());
map = new int[N][M];
iceList = new ArrayList<>();
for(int i=0; i<N; i++) { //๋งต ์
๋ ฅ
st = new StringTokenizer(br.readLine());
for(int j=0; j<M; j++) {
int idx = Integer.parseInt(st.nextToken());
map[i][j] = idx;
if(idx != 0) iceList.add(new int[]{i,j}); //๋น์ฐ ๋ฆฌ์คํธ ์ถ๊ฐ
}
}
while(true) {
isValidate(); //๋น์ฐ ๋ฉ์ด๋ฆฌ ํ์ธ
iceBreak(); //๋น์ฐ ๋
น์ด๋ ๊ณผ์ +1๋
time++; //๊ฑธ๋ฆฐ ์๊ฐ ์ฆ๊ฐ
if(iceList.isEmpty()) { //๋น์ฐ์ด ๋ค๋
น์ ๋ ๊น์ง ํ ๋ฉ์ด๋ฆฌ์ผ ๊ฒฝ์ฐ
System.out.println(0);
break;
}
}
}
private static void iceBreak() {
int[] arr = new int[iceList.size()]; //๊ฐ์๊ฐ ๋ด์์ค ๋ฐฐ์ด
for(int i=0; i<iceList.size(); i++) {
int[] idx = iceList.get(i); //๋น์ฐ ํ ๊ฐ์ฉ ๊บผ๋ด์
int cnt = 0;
for(int j=0; j<4; j++) { //4๋ฐฉํฅ ํ์ 0์ด ์๋ ์์น์ ๊ฐ์ ํ์
int nx = idx[0] + dx[j];
int ny = idx[1] + dy[j];
if(nx<0 || ny<0 || nx>N-1 || ny>M-1) continue;
if(map[nx][ny] == 0) cnt++;
}
arr[i] = cnt;
}
int id = 0;
for(int element : arr) { //๋น์ฐ์ ๋
น์ด๋ฉด์
int[] idx = iceList.get(id);
int value = map[idx[0]][idx[1]] - element;
if(value < 1) { //0์ดํ๋ก ๊ฐ์ํ ๊ฒฝ์ฐ ๋งต ๊ฐ ๊ฐฑ์ ๋ฐ ๋น์ฐ ๋ฆฌ์คํธ์์ ์ ๊ฑฐ
map[idx[0]][idx[1]] = 0;
iceList.remove(id);
}
else { //๋งต ๊ฐ๋ง ๊ฐฑ์ ๋ฐ ์ธ๋ฑ์ค ํฌ์ธํฐ ์ฆ๊ฐ
map[idx[0]][idx[1]] = value;
id++;
}
}
}
private static void isValidate() {
Queue<int[]> queue = new ArrayDeque<>();
boolean[][] v = new boolean[N][M];
int cnt = 0;
for(int[] element : iceList) { //๋ชจ๋ ๋น์ฐ์ ๋ํด์
if(v[element[0]][element[1]]) continue;
cnt++; //๋ฉ์ด๋ฆฌ ๊ฐ์ ์ฒดํฌ
queue.offer(element);
while(!queue.isEmpty()) { //BFS๋ก ๋ฐฉ๋ฌธ์ฒดํฌ
int[] item = queue.poll();
for(int j=0; j<4; j++) {
int nx = item[0] + dx[j];
int ny = item[1] + dy[j];
if(nx<0 || ny<0 || nx>N-1 || ny>M-1 || map[nx][ny] == 0) continue;
if(!v[nx][ny]) {
v[nx][ny] = true;
queue.offer(new int[] {nx,ny});
}
}
}
}
if(cnt > 1) { //๋น์ฐ์ด ๋ ๋ฉ์ด๋ฆฌ ์ด์์ผ ๊ฒฝ์ฐ
System.out.println(time);
System.exit(0);
}
}
}