17144 Samsung sw test
알고리즘
1
2
3
1. 기존 map에서 미세먼지가 있는 부분만, 기존에 있던 미세먼지만 확산시키는 게 관건
2. 따라서 tempMap을 만들어서 map을 복사한 다음에, map에 있는 미세먼지 양을 받아서, tempMap에 확산시키고, 다 확산하면 tempMap을 map에 복사하고 순환하여야 한다.
3. 자꾸 갱신되는 상황을 잊지 말자
코드
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
#include <iostream>
#include <cstring>
#define MAX_WIDTH 50
using namespace std;
int map[MAX_WIDTH][MAX_WIDTH];
int tempMap[MAX_WIDTH][MAX_WIDTH];
int width, height, time;
int airCirculatorRow[2];
int airCirculator();
void diffuseDust(int row, int col);
void runAirCirculator();
int main() {
cin >> height >> width >> time;
int index = 0;
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
cin >> map[i][j];
if (map[i][j] == -1)
airCirculatorRow[index++] = i;
}
}
cout << endl;
cout << airCirculator();
}
int airCirculator() {
for (int second = 0; second < time; second++) {
for (int i = 0; i < height; i++)
memcpy(tempMap[i], map[i], sizeof(int) * width);
//확산
for (int i = 0; i < height; i++)
for (int j = 0; j < width; j++)
if(map[i][j] != 0)
diffuseDust(i, j);
for (int i = 0; i < height; i++)
memcpy(map[i], tempMap[i], sizeof(int) * width);
cout << endl;
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++)
cout << map[i][j] << " ";
cout << endl;
}
//청정기
runAirCirculator();
}
int dust = 0;
for (int i = 0; i < height; i++)
for (int j = 0; j < width; j++)
dust += map[i][j];
return dust + 2;
}
void diffuseDust(int row, int col) {
int count = 0;
int dustDiffusionAmount = map[row][col] / 5;
if (row > 0 && tempMap[row - 1][col] != -1) {
tempMap[row - 1][col] += dustDiffusionAmount;
count++;
}
if (col < width - 1) {
tempMap[row][col + 1] += dustDiffusionAmount;
count++;
}
if (row < height - 1 && tempMap[row + 1][col] != -1) {
tempMap[row + 1][col] += dustDiffusionAmount;
count++;
}
if (col > 0 && tempMap[row][col-1] != -1) {
tempMap[row][col - 1] += dustDiffusionAmount;
count++;
}
tempMap[row][col] -= (dustDiffusionAmount * count);
}
void runAirCirculator() {
//위
int temp = map[airCirculatorRow[0]][1];
map[airCirculatorRow[0]][1] = 0;
for (int i = 2; i < width; i++) {
int temp2 = map[airCirculatorRow[0]][i];
map[airCirculatorRow[0]][i] = temp;
temp = temp2;
}
for (int i = airCirculatorRow[0]-1; i >= 0; i--) {
int temp2 = map[i][width - 1];
map[i][width - 1] = temp;
temp = temp2;
}
for (int i = width - 2; i >= 0; i--) {
int temp2 = map[0][i];
map[0][i] = temp;
temp = temp2;
}
for (int i = 1; i < airCirculatorRow[0]; i++) {
int temp2 = map[i][0];
map[i][0] = temp;
temp = temp2;
}
//아래
temp = map[airCirculatorRow[1]][1];
map[airCirculatorRow[1]][1] = 0;
for (int i = 2; i < width; i++) {
int temp2 = map[airCirculatorRow[1]][i];
map[airCirculatorRow[1]][i] = temp;
temp = temp2;
}
for (int i = airCirculatorRow[1] + 1; i < height; i++) {
int temp2 = map[i][width - 1];
map[i][width - 1] = temp;
temp = temp2;
}
for (int i = width - 2; i >= 0; i--) {
int temp2 = map[height - 1][i];
map[height - 1][i] = temp;
temp = temp2;
}
for (int i = height - 2; i > airCirculatorRow[1]; i--) {
int temp2 = map[i][0];
map[i][0] = temp;
temp = temp2;
}
}