https://www.acmicpc.net/problem/17144
17144번: 미세먼지 안녕!
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 공기청정기는 항상 왼쪽 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼
www.acmicpc.net
이런 문제는 그냥 문제를 잘 읽고 하라는 대로만 하면 풀리는 문제입니다.
미세먼지 확산은 그위치에서 네 방향으로 확산을 하는데
확산하는 방향에 공기청정기가 있거나 칸을 벗어난다거나 하면 그 위치로는
확산을 하지 않고 확산양은 그 위치의 미세먼지 양/ 5 몫을 취하면 됩니다.
확산을 하고 현재 위치의 미세먼지 양은 미세먼지 양 - (미세먼지 양 /5)* 확산한 개수
로 해주시면 됩니다.
공기청정기가 그 뒤에 작동을 하는데 위쪽은 반시계 방향 방향으로
아래쪽은 시계방향으로 위치의 숫자를 한 칸씩 이동하면 되고
이동하는 숫자가 공기청정기 쪽으로 가면 그냥 사라지게 하면 됩니다
그리고 여기서 T가 입력으로 주어지는데 T초 후 남은 미세먼지 양을 출력하면 되는 것으로
공기청정기 -1을 제외한 숫자를 모두 더하고 출력하면 됩니다. 정말 간단하지 않습니까?
방식은 bfs나 dfs 같은 탐색 같은 것 을 해보셨다면 큐를 쓰지 않고 0,0 인덱스부터
미세먼지를 만나면 거기서부터 4방향을 확인해서 갈 수 있으면 확산시키고 미세먼지 양 줄이는 것을
처음에 받은 맵에 하면 지문에서 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다를
위배하게 되고 값이 달라지기 때문에 다른 배열에 저장하여 더하는 식으로 하시면 됩니다.
여기서 한 가지만 이런 식으로 확산이 된다를 설명해드리고 나머지 공기청정기 순환에 대해서 설명드리겠습니다.
지문을 보면 3 X 3 배열에 미세먼지 확산하는 법을 그림으로 설명해놨습니다.
거기에 대한 설명입니다.
이런 식으로 확산을 하시면 됩니다.
그렇다면 공기의 흐름은 어떤 식으로 하면 될까요?
이런 식으로 공기 흐름을 하시면 되고 공기 2의 흐름은
dir만 바꿔주고 범위만 잘 체크해주시면 금방 구현이 가능합니다.
공기 흐름 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
166
167
168
169
170
171
172
173
174
175
176
177
178
|
#include<stdio.h>
#include<string.h>
using namespace std;
int r, c, t;
int map[54][54];
struct AirClean {
int y, x;
}Clean[2];
int idx = 0;
int idx1 = 0;
void init()
{
scanf("%d %d %d", &r, &c, &t);
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
scanf("%d", &map[i][j]);
if (map[i][j] == -1) {
Clean[idx].y = i;
Clean[idx].x = j;
idx++;
}
}
}
}
int dust[54][54] = { 0, };
AirClean Dust[2540] = { 0, };
int dy[4] = { 1,0,-1,0 };//V<^>
int dx[4] = { 0,-1,0,1 };
/*
00 01 02
10 11 12
20 21 22
*/
int main(void)
{
init();
while (t--) {
memset(dust, 0, sizeof(dust));
memset(Dust, 0, sizeof(Dust));
idx1 = 0;
for (int y = 0; y < r; y++) {
for (int x = 0; x < c; x++) {
if (map[y][x] != -1 && map[y][x] != 0) {
Dust[idx1].y = y;
Dust[idx1].x = x;
idx1++;
}
}
}
for (int i = 0; i < idx1; i++) {
int cnt = 0;
if (map[Dust[i].y][Dust[i].x] / 5 != 0) {
for (int d = 0; d < 4; d++) {
int ny = Dust[i].y + dy[d];
int nx = Dust[i].x + dx[d];
if (0 <= ny && ny < r && 0 <= nx && nx < c) {
if (map[ny][nx] != -1) {
dust[ny][nx] += map[Dust[i].y][Dust[i].x] / 5;
cnt++;
}
}
}
map[Dust[i].y][Dust[i].x] = map[Dust[i].y][Dust[i].x] - (map[Dust[i].y][Dust[i].x] / 5)*cnt;
}
}
for (int y = 0; y < r; y++) {
for (int x = 0; x < c; x++) {
map[y][x] += dust[y][x];
}
}
//1번 공기 회전
int ry = 0;
int y =ry= Clean[0].y;
int x = Clean[0].x;
int dir = 0;
while (1) {
int ny =y- dy[dir];
int nx =x- dx[dir];
if (map[ny][nx] == -1)break;
if (0<=ny && ny <=ry &&0<=nx && nx < c) {
if(map[y][x]!=-1)map[y][x] = map[ny][nx];
map[ny][nx] = 0;
y = ny;
x = nx;
}
else {
dir++;
dir = (dir + 4) % 4;
}
}
//2번 공기 회전
y =ry= Clean[1].y;
x =Clean[1].x;
dir = 2;
while (1) {
int ny = y - dy[dir];
int nx = x - dx[dir];
if (map[ny][nx] == -1)break;
if (ry<= ny && ny <r&& 0 <= nx && nx <c) {
if (map[y][x] != -1)map[y][x] = map[ny][nx];
map[ny][nx] = 0;
y = ny;
x = nx;
}
else {
dir--;
dir = (dir + 4) % 4;
}
}
/*
for (int i = Clean[0].y - 1; i >= 0; i--) {
if (map[i + 1][Clean[0].x] != -1)
{
map[i + 1][Clean[0].x] = map[i][Clean[0].x];
map[i][Clean[0].x] = 0;
}
}
for (int i = 1; i < c; i++) {
map[0][i - 1] = map[0][i];
map[0][i] = 0;
}
for (int i = 1; i <= Clean[0].y; i++) {
map[i - 1][c - 1] = map[i][c - 1];
map[i][c - 1] = 0;
}
for (int i = c - 2; i >= 0; i--) {
if (map[Clean[0].y][i] != -1) {
map[Clean[0].y][i + 1] = map[Clean[0].y][i];
map[Clean[0].y][i] = 0;
}
}
for (int i = Clean[1].y + 1; i < r; i++) {
if (map[i - 1][Clean[1].x] != -1) {
map[i - 1][Clean[1].x] = map[i][Clean[1].x];
map[i][Clean[1].x] = 0;
}
}
for (int i = Clean[1].x + 1; i < c; i++) {
map[r - 1][i - 1] = map[r - 1][i];
map[r - 1][i] = 0;
}
for (int i = r - 2; i >= Clean[1].y; i--) {
map[i + 1][c - 1] = map[i][c - 1];
map[i][c - 1] = 0;
}
for (int i = c - 2; i >= 0; i--) {
if (map[Clean[1].y][i] != -1) {
map[Clean[1].y][i + 1] = map[Clean[1].y][i];
map[Clean[1].y][i] = 0;
}
}
*/
}
long long cnt = 0;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (map[i][j] != -1 && map[i][j] != 0) {
cnt += map[i][j];
}
}
}
printf("%lld\n", cnt);
return 0;
}
|
|
소스 코드를 보시면 주석 처리되어있는 부분이 있습니다. 그 부분은 내가 도저히 모르겠다.
그냥 한 구역 씩 포문을 돌려서 하겠다 하면 포문을 이용해서 하시면 됩니다.
하지만 while 문 하나로 가능하니 while방식에 익숙해지시는 것을 추천드립니다.
지금 시점에서는 뜸하지만 이전까지 미세먼지로 고생 많으셨는데 알고리즘 풀이를 통해
상쾌하게 먼지를 제거해 보시기 바랍니다.
그럼 오늘은 여기까지 입니다.
감사합니다.
'알고리즘 모음집 > 알고리즘 (Algorithm)' 카테고리의 다른 글
| 백준 2668 숫자 고르기 (8) | 2019.07.16 |
|---|---|
| 백준 17136 색종이 붙이기 (0) | 2019.07.12 |
| 백준 17143 낚시왕 (0) | 2019.07.12 |
| 백준 16939 2×2×2 큐브 (0) | 2019.07.12 |
| 백준 17140 이차원 배열과 연산 (0) | 2019.07.09 |
댓글