https://www.acmicpc.net/problem/17144
17144번: 미세먼지 안녕!
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 공기청정기는 항상 왼쪽 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼
www.acmicpc.net
처음에 큐를 사용하지 않고 벡터로 구현을 했어서 헤맸던 문제였다...
공기청정기 바람 나오는 거 구현할 때에도 범위 때문에 계속 헷갈렸었다
공기청정기는 위쪽과 아래쪽을 나눠서 각각 구현해줬다. 그냥 문제에서 시키는 대로 한 칸씩 이동시켜주면 된다.
미세먼지 확산의 경우에는 확산되는 먼지는 따로 저장해서 나중에 한번에 더해줘야 한다.
바로 더해주면 확산된 곳에서 같은 시간에 다시 확산될 수 도 있기 때문이다
이 부분이랑 공기청정기에서 바람 나와서 이동할 때 범위만 조심해주면 될 것 같다!
|
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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
|
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
int R, C, T;
int map[50][50];
int sum[50][50];
int air[2];
int dx[] = { 0,-1,0,1 };
int dy[] = { 1,0,-1,0 };
void goUpair() {
int x, y;
x = air[0] - 1;
y = 0;
if (x < 0) return;
while (x > 0) {
map[x][y] = map[x - 1][y];
x--;
}
while (y < C - 1) {
map[x][y] = map[x][y + 1];
y++;
}
while (x < air[0]) {
map[x][y] = map[x + 1][y];
x++;
}
while (y > 1) {
map[x][y] = map[x][y - 1];
y--;
}
map[x][1] = 0;
}
void goDownair() {
int x, y;
x = air[1] + 1;
y = 0;
if (x >= R) return;
while (x < R - 1) {
map[x][y] = map[x + 1][y];
x++;
}
while (y < C - 1) {
map[x][y] = map[x][y + 1];
y++;
}
while (x > air[1]) {
map[x][y] = map[x - 1][y];
x--;
}
while (y > 1) {
map[x][y] = map[x][y - 1];
y--;
}
map[x][1] = 0;
}
void spread() {
queue<pair<int, int>> q;
//먼지가 있는 곳을 모두 큐에 넣어준다.
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (map[i][j] > 0) {
q.push(make_pair(i, j));
}
}
}
int x, y;
while (!q.empty()) {
x = q.front().first;
y = q.front().second;
q.pop();
int amt = map[x][y] / 5;
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
if (map[nx][ny] == -1) continue;
//확산될때 원래자리에서는 빼주고
//확산될 자리에서는 더해준다.
map[x][y] -= amt;
sum[nx][ny] += amt;
}
}
//확산된 먼지들을 더해준다.
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
map[i][j] += sum[i][j];
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> R >> C >> T;
bool flag = true;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
cin >> map[i][j];
if (map[i][j] == -1) {
if (flag) {
//첫번째 공기청정기
air[0] = i;
flag = false;
}
else {
//두번째 공기청정기
air[1] = i;
}
}
}
}
//T초 동안 확산과 공기청정(위쪽, 아래쪽)을 반복
for (int i = 0; i < T; i++) {
memset(sum, 0, sizeof(sum));
spread();
goUpair();
goDownair();
}
//남아있는 먼지 수를 계산
int ans = 0;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
ans += map[i][j];
}
}
//공기청정기 2개때문에 빠진 값을 다시 더해준다.
cout << ans + 2 << '\n';
return 0;
}
Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 17135. 캐슬 디펜스 (0) | 2019.08.01 |
|---|---|
| [BOJ] 16236. 아기 상어 (0) | 2019.07.31 |
| [BOJ] 17140. 이차원 배열과 연산 (0) | 2019.07.30 |
| [BOJ] 17142. 연구소 3 (0) | 2019.07.30 |
| [BOJ] 1806. 부분합 (0) | 2019.07.16 |
