#17144. 미세먼지 안녕!
Problem
- 공기청정기 항상 왼쪽 열 (두 행 차지)
- 그외 미세먼지나 빈 칸이 존재
- 1초 동안 일어나는 일
- 미세먼지 확산
4방향(상하좌우)
공기청정기나 경계를 벗어나는 칸은 확산이 일어나지 않음
미세먼지 양/5 만큼 확산된다. (각 방향에 대해 한 칸)
확산된 후 남은 미세먼지 양은
현재 미세먼지 양 - 현재 미세먼지 양/5 * 확산된 방향 개수 - 공기청정기 작동 (바람)
위쪽 → 반시계방향 순환
아래쪽 → 시계방향 순환
미세먼지가 바람의 방향대로 한 칸씩 이동
미세먼지가 공기청정기로 들어가면 모두 정화
Goal: T초가 지난 후 남아있는 미세먼지의 양
Solution
1초가 지날 때마다 다음과 같은 작업이 수행된다.
- 미세먼지 확산
- 바람으로 인한 이동
- 미세먼지 확산
5 이상인 값만 확산이 일어난다.
확산이 일어나기 전에 queue에 이 값과 이 값이 있는 위치를 저장해놓는다.
(값을 저장해야 올바른 값을 구할 수 있음)
queue에서 하나씩 꺼내어 4가지 방향을 확인한다.
(공기청정기 있는 곳과 경계를 넘는 곳은 불가능)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17void spread() {
int len = q.size();
for (int i = 0; i < len; ++i) {
int r = q.front().r;
int c = q.front().c;
int mid = q.front().value;
q.pop();
for (int j = 0; j < 4; ++j) {
int x = r + dx[j];
int y = c + dy[j];
if (isBound(x, y) && map[x][y] != -1) {
map[x][y] += mid / 5;
map[r][c] -= mid / 5;
}
}
}
}
확산이 가능하다면 연산을 수행한다.
- 바람으로 인한 이동
아래 순서대로 map을 바꿔준다.
공기청정기로 들어간다는 것은 굳이 값을 바꿔줄 필요 없이 전의 값이 이를 덮어주기만 하면 된다. (1번째) → 아래 2번 화살표가 잘못되었습니다….(반대입니다)
공기청정기에서 나아가는 바람으로(4번째) 값을 0으로 채워주어야 한다.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
32void wind() {
int i, j, clean_row = clean[0];
// 위쪽
for (i = clean_row - 2; i >= 0; --i) {
map[i + 1][0] = map[i][0];
}
for (j = 1; j < total_col; ++j) {
map[0][j - 1] = map[0][j];
}
for (i = 1; i <= clean_row; ++i) {
map[i - 1][total_col - 1] = map[i][total_col - 1];
}
for (j = total_col - 1; j >= 1; --j) {
map[clean_row][j + 1] = map[clean_row][j];
}
// 아래쪽
map[clean_row][1] = 0;
clean_row = clean[1];
for (i = clean_row + 2; i < total_row; ++i) {
map[i - 1][0] = map[i][0];
}
for (j = 1; j < total_col; ++j) {
map[total_row - 1][j - 1] = map[total_row - 1][j];
}
for (i = total_row - 2; i >= clean_row; --i) {
map[i + 1][total_col - 1] = map[i][total_col - 1];
}
for (j = total_col - 2; j >= 1; --j) {
map[clean_row][j + 1] = map[clean_row][j];
}
map[clean_row][1] = 0;
}
1 Try
1 |
|
테스트 케이스는 다 맞다는데 틀렸단다…ㅎ
그 이유는 MAX를 50이기 때문이다. (응? 뭔 🙄🤔…다음부터 넉넉히 잡자..)
MAX 51로 고쳐주니까 바로 정답 처리 되었다.
2 Try
1 |
|
Debug
- 코드
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
using namespace std;
int total_row, total_col, time;
int map[MAX][MAX];
int clean[2]; // 공기청정기 위치(무조건 0열)
struct info {
int r, c, value;
};
queue<info> q;
// 상하좌우
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
bool isBound(int r, int c) {
if (r > -1 && c > -1 && r < total_row && c < total_col) return true;
return false;
}
// 1. 미세먼지 확산
void spread() {
int len = q.size();
for (int i = 0; i < len; ++i) {
int r = q.front().r;
int c = q.front().c;
int mid = q.front().value;
q.pop();
for (int j = 0; j < 4; ++j) {
int x = r + dx[j];
int y = c + dy[j];
if (isBound(x, y) && map[x][y] != -1) {
map[x][y] += mid / 5;
map[r][c] -= mid / 5;
}
}
}
}
// 2. 바람으로 미세먼지 이동
void wind() {
// 위쪽 ( 반시계 작업은 거꾸로 수행, 그래야 편함)
int i, j, clean_row = clean[0];
for (i = clean_row - 2; i >= 0; --i) { // 공기청정기에 들어가면 사라지니까 바로 이전건 그냥 덮어쓰면 됨
map[i + 1][0] = map[i][0];
}
for (j = 1; j < total_col; ++j) {
map[0][j - 1] = map[0][j];
}
for (i = 1; i <= clean_row; ++i) {
map[i - 1][total_col - 1] = map[i][total_col - 1];
}
for (j = total_col - 1; j >= 1; --j) {
map[clean_row][j + 1] = map[clean_row][j];
}
map[clean_row][1] = 0;
// 아래쪽 ( 시계 )
clean_row = clean[1];
for (i = clean_row + 2; i < total_row; ++i) {
map[i - 1][0] = map[i][0];
}
for (j = 1; j < total_col; ++j) {
map[total_row - 1][j - 1] = map[total_row - 1][j];
}
for (i = total_row - 2; i >= clean_row; --i) {
map[i + 1][total_col - 1] = map[i][total_col - 1];
}
for (j = total_col - 2; j >= 1; --j) {
map[clean_row][j + 1] = map[clean_row][j];
}
map[clean_row][1] = 0;
}
int main() {
int answer, idx = 0;
scanf("%d %d %d", &total_row, &total_col, &time);
for (int i = 0; i < total_row; ++i) {
for (int j = 0; j < total_col; ++j) {
scanf("%d", &map[i][j]);
if (map[i][j] >= 5) q.push({ i, j, map[i][j] });
}
if (map[i][0] == -1) clean[idx++] = i;
}
while (time--) {
answer = 0;
spread();
wind();
printf("change\n");
for (int i = 0; i < total_row; ++i) {
for (int j = 0; j < total_col; ++j) {
printf("%d ", map[i][j]);
if (map[i][j] > 0) answer += map[i][j];
if (map[i][j] >= 5) q.push({ i, j, map[i][j] });
}
printf("\n");
}
}
printf("%d\n", answer);
return 0;
} - 바람에 의한 이동 확인용 test case
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
177 8 1
2 4 0 0 0 0 0 9
3 0 0 0 3 0 0 8
-1 3 5 0 0 0 22 0
-1 8 0 0 0 0 0 3
3 0 0 0 0 10 43 5
4 0 5 0 15 0 0 0
2 1 40 0 0 0 20 3
// output
Change
4 0 0 0 0 0 9 8
2 0 0 0 3 0 0 0
-1 0 3 5 0 0 0 22
-1 0 8 0 0 0 0 0
4 0 0 0 0 10 43 3
2 0 5 0 15 0 0 5
1 40 0 0 0 20 3 01
2
3
4
5
6
7
8
9
10
11
12
13
146 6 1
5 0 3 4 1 2
0 0 7 0 0 3
-1 10 0 46 0 2
-1 0 0 0 0 4
3 0 0 0 0 3
1 3 1 2 4 2
change!!
3 1 4 4 1 2
1 3 3 10 0 3
-1 4 12 10 9 2
-1 2 0 9 0 4
3 0 0 0 0 3
1 3 1 2 4 2