문제
풀이
1초동안 아래의 두가지 일이 일어난다.
-
미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
- (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
- 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
- 확산되는 양은 Ar,c/5이고 소수점은 버린다.
- (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.
-
공기청정기가 작동한다.
- 공기청정기에서는 바람이 나온다.
- 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
- 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
- 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.
우선 미세먼지가 확산되는 것을 살펴보자.
- 미세먼지 확산
미세먼지의 확산은 순서대로 시행되는 것이 아니라 모두 동시에 일어난다는 점을 주의해야 한다.
예를 들어 30의 먼지가 있고, 그 오른쪽에 5의 먼지가 있다고 가정해보자.
30/5 = 6의 먼지가 주변에 더해지게 되는데, 만일 이 6을 오른쪽 먼지 5에 더한 상태에서 5의 확산을 계산하면 11/5 = 2씩 확산이 일어난다.
이렇게 하는것이 아니라 모두 동시에 일어나야 하므로 6을 더하기 전 원래 값인 5의 값에서 확산이 일어나야 한다.
이를 위해 확산하는 값을 저장하는 2차원 배열 add 를 따로 만들었다.
1
int add[51][51];
아래의 그림들을 통해 좀 더 자세히 살펴보자.
원본배열 room에서 이중 for문을 통해 순차적으로 확산을 계산한다. 확산량을 add 배열에 저장하여 루프를 다 돌면 room에 전부 더해준다.
30/5 = 6 이므로 주변으로 6씩 퍼지고 자신은 6 x 3 = 18 만큼 빼준다.
7/5 = 1, 2칸에 퍼졌으므로 자신의 위치는 2 x 1 만큼 add에서 빼준다.
10/5 = 2 이므로 주변에 2씩 퍼진다. 3칸에 퍼졌으므로 자신의 위치는 3 x 2 = 6 만큼 빼준다.
마찬가지로 20도 위와 같이 수행한다.
한번의 루프를 다 돌았으면 add의 값을 room 에 더해주고, add를 0으로 초기화해준다.
1
2
3
4
5
6
7
8
9
// 미세먼지 확산 업데이트
for (int i = 0; i < r; i++)
{
for (int j = 0; j < c; j++)
{
room[i][j] += add[i][j];
add[i][j] = 0; // 0으로 초기화
}
}
- 공기청정기에 의한 먼지들의 이동
이 부분은 그냥 줄마다 for문을 통해 수행해줬다. 그냥 값을 일일이 밀어주는 코드이기 때문에 코드를 보면 쉽게 이해할 수 있다.
소스 코드
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
#include <iostream>
using namespace std;
int r, c, t;
int room[51][51];
int add[51][51];
int dr[4] = {0, 1, 0, -1};
int dc[4] = {-1, 0, 1, 0};
int up_row, down_row; // 공기청정기 윗부분과 아랫부분의 행
int total_dust; // 총 먼지량
void input()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> r >> c >> t;
bool flag = false;
for (int i = 0; i < r; i++)
{
for (int j = 0; j < c; j++)
{
cin >> room[i][j];
if (room[i][j] == -1)
{
if (!flag)
{
up_row = i;
flag = true;
}
else
down_row = i;
}
else
total_dust += room[i][j];
}
}
}
// 먼지의 확산 함수
void spreadDust()
{
// 미세먼지 확산량 계산
for (int i = 0; i < r; i++)
{
for (int j = 0; j < c; j++)
{
int cnt = 0;
int val = room[i][j] / 5;
if (room[i][j] == 0 || room[i][j] == -1)
continue;
for (int k = 0; k < 4; k++)
{
int nr = i + dr[k];
int nc = j + dc[k];
if (nr < 0 || nr >= r || nc < 0 || nc >= c)
continue;
if (room[nr][nc] == -1)
continue;
add[nr][nc] += val;
cnt++;
}
add[i][j] -= (cnt * val);
}
}
// 미세먼지 확산 업데이트
for (int i = 0; i < r; i++)
{
for (int j = 0; j < c; j++)
{
room[i][j] += add[i][j];
add[i][j] = 0;
}
}
}
// 공기청정기 순환에 의한 먼지 이동
void airCleaner()
{
// 사라지는 먼지 계산
total_dust -= room[up_row - 1][0];
total_dust -= room[down_row + 1][0];
// 위의 공기 순환 (반시계)
// 1. 왼쪽줄
for (int i = up_row - 1; i > 0; i--)
room[i][0] = room[i - 1][0];
// 2. 윗줄
for (int i = 0; i < c - 1; i++)
room[0][i] = room[0][i + 1];
// 3. 오른쪽줄
for (int i = 1; i <= up_row; i++)
room[i - 1][c - 1] = room[i][c - 1];
// 4. 아랫줄
for (int i = c - 1; i > 1; i--)
room[up_row][i] = room[up_row][i - 1];
room[up_row][1] = 0;
// 아래공기 순환 (시계)
// 1. 왼쪽줄
for (int i = down_row + 1; i < r - 1; i++)
room[i][0] = room[i + 1][0];
// 2. 아랫줄
for (int i = 0; i < c - 1; i++)
room[r - 1][i] = room[r - 1][i + 1];
// 3. 오른쪽줄
for (int i = r - 1; i >= down_row; i--)
room[i][c - 1] = room[i - 1][c - 1];
// 4. 윗줄
for (int i = c - 1; i > 1; i--)
room[down_row][i] = room[down_row][i - 1];
room[down_row][1] = 0;
}
void solve()
{
while (t--)
{
// 미세먼지 확산
spreadDust();
// 공기순환에 의한 미세먼지 이동
airCleaner();
}
cout << total_dust << '\n';
}
int main()
{
input();
solve();
return 0;
}
