미세먼지 안녕!

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 7939 4272 2890 53.988%

문제

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.

img

공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.

1초 동안 아래 적힌 일이 순서대로 일어난다.

  1. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
    • (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
    • 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
    • 확산되는 양은 Ar,c/5이고 소수점은 버린다.
    • (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.
  2. 공기청정기가 작동한다.
    • 공기청정기에서는 바람이 나온다.
    • 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
    • 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
    • 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.

다음은 확산의 예시이다.

img

왼쪽과 오른쪽에 칸이 없기 때문에, 두 방향으로만 확산이 일어났다.

img

인접한 네 방향으로 모두 확산이 일어난다.

img

공기청정기가 있는 칸으로는 확산이 일어나지 않는다.

공기청정기의 바람은 다음과 같은 방향으로 순환한다.

img

방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.

입력

첫째 줄에 R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000) 가 주어진다.

둘째 줄부터 R개의 줄에 Ar,c (-1 ≤ Ar,c ≤ 1,000)가 주어진다. 공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양이다. -1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.

출력

첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.

풀이

아래의 일이 1초 동안 일어난다.

  1. 미세먼지가 모든 칸에서 동시에 일어난다. -> bfs 탐색을 통해서 진행한다.
  2. 공기 청정기의 위쪽은 반시계 방향, 아래쪽은 시계 방향으로 바람이 분다. 이로 인해 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다. -> 이 부분은 그대로 구현을 하면 된다.
  3. 공기 청정기의 위치로 들어간 미세먼지는 정화된다.
  4. 공기 청정기가 움직인 뒤, 바뀐 map 배열을 업데이트 해준다.
  5. T초가 지난 후 방에 남아있는 미세먼지의 양을 출력한다.

문제에서 주의해야 할 점은 원본 배열이 바뀌면 안되기 배열을 복사해서 copy를 이용해서 미세먼지를 확장시키고 난 뒤의 배열을 원본 배열에 업데이트 해준다. 그리고 공기 청정기가 돌면서 정화한 뒤의 배열을 다시 원본 배열에 업데이트 시키는데, 이때 공기 청정기의 바람이 지나가면서 바뀐 부분만 업데이트 하도록 한다.

문제에서 공기 청정기의 바람에 의해 정화된 후, 바뀐 배열을 원본 배열에 업데이트 시킬 때, 변경된 부분만 업데이트 시키려 하는 과정에서 조건문을 ||로 줘야 하는데 && 로 하나를 주면서 20분 정도 해맸다…

풀이

조금 더 시간을 줄일 수 있는 방법이 있다. 위의 풀이에서는 visit 배열을 두어 방문 여부를 체크하고 결국, 다시 초기화 하는 형태였는데 이는 불필요하다.

굳이 bfs 탐색을 하면서 visit 배열을 사용하지 않는 것이다. 어차피 미세먼지의 확산은 동시에 일어나기 때문에 이로 인해서 방문한 곳은 또 방문하게 된다. 따라서 이를 아예 고려하지 않으면 문제가 되지 않는다.

  1. 미세먼지가 있는 곳은 큐에 넣는다.
  2. bfs 탐색을 통하여 미세먼지를 확장한다.
  3. 공기 청정기가 움직이며 바람을 통해 순환시킨다.
  4. 위의 과정을 t 동안 반복하고, 미세 먼지의 양의 합을 구한다.

다만, 주의할 점은 원본 배열이 변경되기 때문에 copy 배열을 만들어서 작업한 후, 원본 배열에 업데이트 시켜줘야 한다는 점이다.

[Code]

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
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

/**
* created by victory_woo on 2020/04/17
* 미세먼지 안녕!
* 삼성 기출.
* 시뮬레이션 + 구현.
*/
public class Problem17144Re {
private static int r, c, t;
private static int[][] map;
private static Node[] cleaners;
private static int[] dx = {-1, 0, 1, 0};
private static int[] dy = {0, 1, 0, -1};

public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] in = br.readLine().split(" ");
r = toInt(in[0]);
c = toInt(in[1]);
t = toInt(in[2]);

map = new int[r][c];
cleaners = new Node[2];
int index = 0;
for (int i = 0; i < r; i++) {
in = br.readLine().split(" ");
for (int j = 0; j < c; j++) {
map[i][j] = toInt(in[j]);
// 공기 청정기의 위치를 저장한다.
if (map[i][j] == -1) cleaners[index++] = new Node(i, j);
}
}

solve();
}

private static void solve() {
for (int i = 0; i < t; i++) {
spreadDust(); // 미세 먼지를 확장한다.
spreadCleaner();
}

getResult();
}

// 미세먼지를 확장시킨다.
// 이를 위해서 copy 배열을 두고 큐에서 꺼내면서 미세 먼지가 동시에 확장되는 것을 구현한다.
private static void spreadDust() {
// 모든 미세먼지는 동시에 확장되기 때문에 copy 배열을 두어 map 배열에서 꺼내면서 확장시킨다.
int[][] copy = new int[r][c];

// 미세 먼지가 존재하는 칸을 큐에 넣는다.
LinkedList<Node> q = new LinkedList<>();
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (map[i][j] > 0) q.add(new Node(i, j));
}
}

// 큐에서 꺼내면서 인접한 네 방향을 검사하면서 미세 먼지를 확장한다.
// 이 과정은 동시에 일어난다.
while (!q.isEmpty()) {
Node dust = q.remove();
int x = dust.x, y = dust.y;

// 확산되는 양.
int amountOfDust = map[x][y] / 5;
int count = 0;

// 인접한 네 방향 검사.
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];

// 범위 검사.
if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;

// 공기 청정기가 아닌 곳은 미세먼지를 확장시킬 수 있으므로, 미세먼지를 확장시킬 수 있는 공간의 갯수를 구한다.
// 그리고 미세먼지가 있는 곳에 확산되는 양을 더해준다.
if (map[nx][ny] != -1) {
count++;
copy[nx][ny] += amountOfDust;
}
}

copy[x][y] += map[x][y] - amountOfDust * count;
}

copyDust(copy);
}

// map <- copy
private static void copyDust(int[][] copy) {
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
map[i][j] = copy[i][j];
}
}

/*System.out.println("== 미세 먼지 확장 ==");
print();*/
}

// 공기 청정기가 바람을 통해서 순환한다.
// !!! 여기는 t가 아니라 공기청정기가 2칸 차지하니까 2여야 함..
private static void spreadCleaner() {
int[][] copy = new int[r][c];
for (int i = 0; i < 2; i++) {
Node cleaner = cleaners[i];
int x = cleaner.x;
int y = cleaner.y + 1;

// 오른쪽으로 끝까지 이동한다.
while (y < c - 1) {
copy[x][y + 1] = map[x][y];
y++;
}

// 반시계 방향의 경우.
if (i == 0) {
// 위로 올라간다.
while (x > 0) {
copy[x - 1][y] = map[x][y];
x--;
}
} else { // 시계 방향의 경우.
while (x < r - 1) {
copy[x + 1][y] = map[x][y];
x++;
}
}

// 왼쪽으로 끝까지 이동한다.
while (y > 0) {
copy[x][y - 1] = map[x][y];
y--;
}

// 반시계 방향의 경우.
if (i == 0) {
while (x < cleaner.x - 1) {
copy[x + 1][y] = map[x][y];
x++;
}
} else { // 시계 방향의 경우.
while (x > cleaner.x + 1) {
// !!! -1로 했었는데, 그게 아니라 +1로 해야 함
// 아래에서 위로 올라가기 때문이다.
copy[x - 1][y] = map[x][y];
x--;
}
}
}

copyCleaner(copy);
}

// 공기 청정기의 바람이 순환하는 경로만 map 배열로 업데이트 시켜준다.
private static void copyCleaner(int[][] copy) {
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (i == 0 || i == r - 1 || j == 0 || j == c - 1 || i == cleaners[0].x || i == cleaners[1].x)
map[i][j] = copy[i][j];
}
}

/*System.out.println("== 공기청정기 동작 후 ==");
print();*/
}

private static void getResult() {
int sum = 0;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (map[i][j] > 0) sum += map[i][j];
}
}

System.out.println(sum);
}

private static int toInt(String value) {
return Integer.parseInt(value);
}

// 확인용.
private static void print() {
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
System.out.print(map[i][j] + " ");
}
System.out.println();
}
}

static class Node {
int x;
int y;

public Node(int x, int y) {
this.x = x;
this.y = y;
}
}
}

참고

  • [백준 미세먼지 안녕!](