반응형
https://www.acmicpc.net/problem/17144
17144번: 미세먼지 안녕!
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 공기청정기는 항상 왼쪽 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼
www.acmicpc.net
본 문제는 삼성 SW 역량 테스트 기출문제로 브루트 포스를 구현하는 문제다. 문제의 조건은 다음과 같다.
- (r, c)에 있는 먼지는 먼지의 양을 x라 할 때, 먼지는 인접한 4개의 칸(상하좌우)으로 x/5 (나머지 생략) 만큼 확산한다.
- 단, 인접한 칸에 공기청정기가 있거나 칸이 없으면 확산할 수 없다.
- 확산한 양 만큼 원래 있던 먼지는 감소한다.
- 공기청정기는 2칸을 차지하며 위쪽은 반시계 방향, 아래쪽은 시계방향으로 공기를 순환시킨다.
- 이때, 공기청정기에 들어오는 먼지는 없어진다.
문제를 설명하기가 코딩하는 것만큼 까다롭다. 자세한 설명은 링크 참조 바란다.
문제를 단순하게 표현하면 다음과 같다.
- 1초 동안 먼지가 확산된다.
- 1초 동안 공기청정기가 작동한다.
이걸 구현해야한다. 공기청정기를 구현하는게 제일 까다로웠다. 공기청정기 구현 순서는 공기청정기로 들어오는 방향 부터 나가는 방향 순으로 for문을 이용하여 구현하였다. 구현할 때, 1 먼지 이동, 1 공기청정기 작동, 2 먼지 이동, 2 공기청정기 작동의 결과를 다 확인하면서 맞게 작동하는지 확인하면서 코딩하였다.
|
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
|
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
int d[51][51];
int a[51][51] = { 0 };
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int main() {
int r, c, t;
scanf("%d %d %d", &r, &c, &t);
queue<pair<int, int>> q;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
scanf("%d", &d[i][j]);
}
}
int cnt = 1;
/*********************
* 1초 동안 먼지 확산.*
* *******************/
while (t--) {
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (d[i][j] != -1 && d[i][j] != 0) {
q.push(make_pair(i, j));
}
}
}
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
int cnt = 0;
q.pop();
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx >= 0 && nx < r && ny >= 0 && ny < c) {
if (d[nx][ny] != -1) {
a[nx][ny] += d[x][y]/5;
cnt += 1;
}
}
}
d[x][y] = d[x][y] - ((d[x][y]/5) * cnt);
}
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (d[i][j] == -1) continue;
d[i][j] += a[i][j];
}
}
memset(a, 0, sizeof(a));
// printf("\n");
// printf("%d\n", cnt);
// printf("먼지 이동\n");
// for (int i = 0; i < r; i++) {
// for (int j = 0; j < c; j++) {
// printf("%d ", d[i][j]);
// }
// printf("\n");
// }
// printf("\n");
/***************************
* 1초 동안 공기청정기 작동.*
* *************************/
int index = 0;
while (d[index][0] != -1) {
index += 1;
}
// 위에서 아래
for (int i = 1; i < index; i++) {
d[index-i][0] = d[index-(i+1)][0];
}
// 위쪽
for (int i = 0; i < c-1; i++) {
d[0][i] = d[0][i+1];
}
// 아래에서 위
for (int i = 0; i < index; i++) {
d[i][c-1] = d[i+1][c-1];
}
// 가운데
for (int i = c-1; i > 1; i--) {
d[index][i] = d[index][i-1];
}
d[index][1] = 0;
// ==================================
// 아래에서 위
for (int i = index+2; i < r-1; i++) {
d[i][0] = d[i+1][0];
}
// 아래쪽
for (int i = 0; i < c; i++) {
d[r-1][i] = d[r-1][i+1];
}
// 위에서 아래
for (int i = r-1; i > index+1; i--) {
d[i][c-1] = d[i-1][c-1];
}
// 가운데
for (int i = c-1; i > 1; i--) {
d[index+1][i] = d[index+1][i-1];
}
d[index+1][1] = 0;
// printf("\n");
// printf("%d\n", cnt);
// printf("공기청정기 작동\n");
// cnt += 1;
// for (int i = 0; i < r; i++) {
// for (int j = 0; j < c; j++) {
// printf("%d ", d[i][j]);
// }
// printf("\n");
// }
// printf("\n");
}
int ans = 0;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (d[i][j] != -1 && d[i][j] != 0) ans += d[i][j];
}
}
printf("%d\n", ans);
}
|
cs |
반응형
'백준' 카테고리의 다른 글
| [백준 1916] 최소비용 구하기, C++ (0) | 2020.02.21 |
|---|---|
| [백준 14891] 톱니바퀴, C++ (0) | 2020.02.20 |
| [백준 1922] 네트워크 연결, C++ (0) | 2020.02.17 |
| [백준 5557] 1학년, C++ (0) | 2020.02.17 |
| [백준 1890] 점프, C++ (0) | 2020.02.17 |
댓글