/
BAEKJOON 16234
83 lines (77 loc) · 2.35 KB
/
BAEKJOON 16234
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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static int N, L, R, sum, ans;
static int[][] map;
static boolean[][] visit;
static int[] dy = { -1, 1, 0, 0 }, dx = { 0, 0, -1, 1 };
static List<Node> list;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
L = Integer.parseInt(st.nextToken());
R = Integer.parseInt(st.nextToken());
map = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
while (true) {
visit = new boolean[N][N]; // 방문을 초기화
boolean check = false; // 인구 조정있었는지 체크하는거 (조정이 없으면 끝난거임 break)
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!visit[i][j]) { //방문 안한곳을 방문해서 리스트에 담고 해당 지점부터 dfs를 한다.
list = new ArrayList<>();
list.add(new Node(i, j));
dfs(i, j);
if (list.size() > 1) { //처음에 방문안한애는 담기기떄문에 1 이상이면 하나의 연합이 생겼으니깐 map 갱신해줘야함
clac();
check = true; //인구 조정했으니깐 ture
}
sum = 0;
}
}
}
if(check)
ans++; // 조정했으니깐 하루 증가 카운드 해줌.
else
break;
}
System.out.println(ans);
}
private static void clac() {
int avg = sum /list.size(); // 평균값을 저장해서 map 갱신해준다.
for (Node n : list) {
map[n.y][n.x] = avg;
}
}
static void dfs(int y, int x) {
sum += map[y][x];
visit[y][x] = true;
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= N || nx >= N || visit[ny][nx])
continue;
int sub = Math.abs(map[ny][nx] - map[y][x]); // 연합 가능한지 비교 계산
if (sub >= L && sub <= R) { // 연합가능 하면 리스트에 추가, dfs 진행
list.add(new Node(ny, nx));
dfs(ny,nx);
}
}
}
static class Node {
int y, x;
Node(int y, int x) {
this.y = y;
this.x = x;
}
}
}