17144번: 미세먼지 안녕!
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사
www.acmicpc.net
1초 동안 다음과 같은 일이 일어납니다.
1. 미세먼지가 확산되며 미세먼지가 있는 모든 칸에서 동시에 일어납니다.
- 인접한 4방향으로 확산됩니다.
- 인접한 방향이 맵 밖이거나 공기청정기가 있는 곳이라면 확산이 일어나지 않습니다.
- 확산되는 양은 list[i][j] / 5입니다. (소수점 버림)
- (i, j)에 남은 미세먼지 양은 list[i][j] - (list[i][j] / 5) * (확산된 방향의 갯수)입니다.
2. 공기청정기가 작동됩니다.
- 위쪽 공기청정기의 바람은 반시계방향으로 순환, 아래쪽 공기청정기의 바람은 시계방향으로 순환합니다.
- 미세먼지가 바람의 방향대로 한 칸씩 이동합니다.
- 공기청정기로 들어가는 미세먼지는 정화됩니다.
위의 모든것을 직접 구현해야합니다.
우선 2중for문을 돌면서 미세먼지를 확산시킵니다. 이 때 확산이 동시에 일어나야하므로 nextlist라는 변수를 사용하였습니다.
그 다음 공기청정기를 작동시켜 위쪽에는 반시계방향으로, 아래쪽에는 시계방향으로 값을 회전시켜줍니다.
이 과정을 T번 반복하여 T초 후 남아있는 미세먼지 양을 출력합니다.
|
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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int list[][] = new int[51][51];
static int nextlist[][] = new int[51][51];
static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
static int cleaner[][] = new int[2][2];
static int N, M, T;
static void clear() {
int x = cleaner[0][0];
int y = cleaner[0][1];
x--;
int d = 3;
while (true) {
int nx = x + direct[d][0];
int ny = y + direct[d][1];
if (nx <= 0 || ny <= 0 || nx > cleaner[0][0] || ny > M) {
d = (d + 1) % 4;
continue;
}
list[x][y] = 0;
if (list[nx][ny] == -1)
break;
list[x][y] = list[nx][ny];
x = nx;
y = ny;
}
x = cleaner[1][0];
y = cleaner[1][1];
x++;
d = 1;
while (true) {
int nx = x + direct[d][0];
int ny = y + direct[d][1];
if (nx < cleaner[1][0] || ny <= 0 || nx > N || ny > M) {
d = (d + 3) % 4;
continue;
}
list[x][y] = 0;
if (list[nx][ny] == -1)
break;
list[x][y] = list[nx][ny];
x = nx;
y = ny;
}
}
static void spread() {
for (int i = 1; i <= N; i++)
Arrays.fill(nextlist[i], 0);
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (list[i][j] > 0) {
int diff = list[i][j] / 5;
int cnt = 0;
for (int d = 0; d < 4; d++) {
int nx = i + direct[d][0];
int ny = j + direct[d][1];
if (nx <= 0 || ny <= 0 || nx > N || ny > M)
continue;
if (list[nx][ny] == -1)
continue;
nextlist[nx][ny] += diff;
cnt++;
}
nextlist[i][j] += (list[i][j] - diff * cnt);
}
}
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (list[i][j] == -1)
continue;
list[i][j] = nextlist[i][j];
}
}
}
static void func() {
for (int t = 1; t <= T; t++) {
spread();
clear();
}
}
static void print() {
int ans = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (list[i][j] > 0)
ans += list[i][j];
}
}
System.out.println(ans);
}
static void input() throws Exception {
int t = 0;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
T = Integer.parseInt(st.nextToken());
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= M; j++) {
list[i][j] = Integer.parseInt(st.nextToken());
if (list[i][j] == -1) {
cleaner[t][0] = i;
cleaner[t++][1] = j;
}
}
}
}
public static void main(String[] args) throws Exception {
input();
func();
print();
}
}
|
cs |
'algorithm > Implementation' 카테고리의 다른 글
| boj 17143 낚시왕 (0) | 2021.04.23 |
|---|---|
| boj 20207 달력 (0) | 2021.04.22 |
| boj 2564 경비원 (0) | 2021.04.13 |
| boj 16719 ZOAC (0) | 2021.03.15 |
| boj 3085 사탕 게임 (0) | 2021.02.26 |