Algorithm_Practice/16234.java at master · ktyu/Algorithm_Practice · GitHub

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
100
101
102
103
104
105
106
107
108
109
110
importjava.util.*;

publicclassMain {

staticclassPoint {
intx,y;
Point(intx, inty) {this.x=x; this.y=y;}
 }
publicstaticvoidmain(String[] args) {

Scannersc = newScanner(System.in);

// 입력 받기
n = sc.nextInt();
l = sc.nextInt();
r = sc.nextInt();

map = newint[n][n];
for(inti=0; i<n; i++) {
for(intj=0; j<n; j++) {
map[i][j] = sc.nextInt();
 }
 }

intday = 0;
booleanchanged;

// 현재 map의 상태에서 에서 연합을 이룰 것들을 검사
do {
changed = false;
check = newboolean[n][n];
int[][] map_new = newint[n][n];

for(inti=0; i<n; i++) {
for(intj=0; j<n; j++) {
// 아래 재귀호출 도중에 연합을 이뤄낸 국가이면 다시 방문할 필요없음
if(check[i][j])
continue;

// 연합을 이룰 국가들의 리스트
List<Point> union = newArrayList<>();
union.add(newPoint(i, j));
check[i][j] = true;

// 연합 가능한 국가를 DFS로 찾고 없으면 끝
dfs(union, i, j);
if(union.size() == 1)
continue;

// 국경을 열어야할 나라들이 존재하는 경우 map_new에 기록
changed = true;
intsum = 0;
for(Pointp : union) {
sum += map[p.x][p.y];
 }
sum /= union.size();

for(Pointp : union) {
map_new[p.x][p.y] = sum;
 }
 }
 }

// 연합하지 못한 국가는 기존의 값을 덮어씀
for(inti=0; i<n; i++) {
for(intj=0; j<n; j++) {
if (map_new[i][j] == 0)
map_new[i][j] = map[i][j];
 }
 }

// 새 맵으로 갱신하고, 바뀐점이 있는지 체크
map = map_new;
if(changed)
day++;

 } while(changed);


System.out.println(day);
 }

staticint[] dx = {1, 0, -1, 0};
staticint[] dy = {0, 1, 0, -1};

staticintn;
staticintl;
staticintr;

staticboolean[][] check;
staticint[][] map;

staticvoiddfs(List<Point> union, intx, inty) {

for(inti=0; i<4; i++) {
intxx = x+dx[i];
intyy = y+dy[i];

if(xx<0 || xx>=n || yy<0 || yy>=n || check[xx][yy])
continue;

intval = Math.abs(map[x][y] - map[xx][yy]);
if(l <= val && val <= r) {
union.add(newPoint(xx, yy));
check[xx][yy] = true;
dfs(union, xx, yy);
 }
 }
 }
}