시뮬레이션과 구현
미세먼지 안녕!
4gats
2023. 9. 27. 09:45
https://www.acmicpc.net/problem/17144
17144번: 미세먼지 안녕!
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사
www.acmicpc.net
1. 확산 그냥 조건 대로 시켜주면 되겠는데?
라고 생각하면 답이 나오지 않았다..
확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다
1. c_map을 만들어서 확산 전에 배열 복사를 시켜준다.
2. map을 기준으로 확산을 돌리고
3. 결과값은 c_map에 저장한다.
4. map에 c_map을 다시 복사시키면 끝
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
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
159
160
161
162
163
164
165
|
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
int map[55][55];
int c_map[55][55];
int r, c, t;
struct info {
int row;
int col;
};
vector<info> machine;
void expansion()
{
// 맵 복사
memcpy(c_map, map, sizeof(c_map));
for (int i = 0; i < r; i++)
{
for (int j = 0; j < c; j++)
{
if (map[i][j] > 0)
{
int yang = map[i][j] / 5;
if (yang == 0)
continue;
else
{
int dir_cnt = 0;
for (int k = 0; k < 4; k++)
{
int nx = i + dx[k];
int ny = j + dy[k];
if (nx >= 0 && nx < r && ny >= 0 && ny < c && map[nx][ny] != -1)
{
c_map[nx][ny] += yang;
dir_cnt++;
}
}
c_map[i][j] -= (yang * dir_cnt);
}
}
}
}
memcpy(map, c_map, sizeof(map));
}
void move()
{
for (int idx = 0; idx < 2; idx++)
{
// 반시계 방향
if (idx == 0)
{
// 공기청정기 위에서부터 (0, 0)까지
for (int i = machine[idx].row - 1; i > 0; i--)
{
map[i][0] = map[i - 1][0];
}
// 왼쪽
for (int j = 0; j < c - 1; j++)
{
map[0][j] = map[0][j + 1];
}
// 위
for (int i = 1; i <= machine[idx].row; i++)
{
map[i - 1][c - 1] = map[i][c - 1];
}
// 오른쪽
for (int j = c - 1; j > 1; j--)
{
map[machine[idx].row][j] = map[machine[idx].row][j - 1];
}
map[machine[idx].row][1] = 0;
}
// 시계 방향
else
{
// 위
for (int i = machine[idx].row + 1; i < r - 1; i++)
{
map[i][0] = map[i + 1][0];
}
// 왼쪽
for (int j = 0; j < c - 1; j++)
{
map[r - 1][j] = map[r - 1][j + 1];
}
// 아래
for (int i = r - 1; i >= machine[idx].row; i--)
{
map[i][c - 1] = map[i - 1][c - 1];
}
// 오른쪽
for (int j = c - 1; j > 1; j--)
{
map[machine[idx].row][j] = map[machine[idx].row][j - 1];
}
map[machine[idx].row][1] = 0;
}
}
}
int calculate()
{
int hap = 0;
for (int i = 0; i < r; i++)
{
for (int j = 0; j < c; j++)
{
if (map[i][j] == -1 || map[i][j] == 0)
continue;
else
hap += map[i][j];
}
}
return hap;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> r >> c >> t;
for (int i = 0; i < r; i++)
{
for (int j = 0; j < c; j++)
{
cin >> map[i][j];
if (map[i][j] == -1)
{
machine.push_back({ i,j });
}
}
}
for (int x = 0; x < t; x++)
{
expansion();
move();
}
cout << calculate() << '\n';
return 0;
}
|
cs |