https://www.acmicpc.net/problem/17144
17144번: 미세먼지 안녕하세요!
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려 한다.
공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타내고 1×1 크기의 구획으로 나누었다.
구사
www.acmicpc.net
문제
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려 한다.
공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타내고 1×1 크기의 구획으로 나누었다.
구사과는 뛰어난 코딩 기술을 이용하여 각 매스(r, c)에 있는 미세먼지의 양을 실시간으로 감시하는 시스템을 개발했다.
(r, c)는 r행의 c열을 의미합니다.
공기 청정기는 항상 한 줄에 설치되며 크기는 두 줄을 차지합니다.
공기 청정기가 설치되지 않은 매스에는 미세먼지가 있으며 (r,c)의 미세먼지 양은 $A_{r,c}$입니다.
1초간 아래에 쓴 것이 순차적으로 일어난다.
- 미세먼지가 확산된다.
확산은 미세먼지가 있는 모든 송어에서 동시에 일어난다.
- (r, c)의 미세먼지는 인접한 4방향으로 확산한다.
- 인접한 방향으로 공기 청정기가 있거나, 캔스가 없으면 그 방향으로는 확산이 일어나지 않는다.
- 확산되는 양은 $A_{r,c}/5$이고 소수점은 버린다.
- (r, c)에 남는 미분진의 양은, $A_{r,c} – (A_{r,c}/5)$×(확산 방향의 수)이다.
- (r, c)의 미세먼지는 인접한 4방향으로 확산한다.
- 공기 청정기가 작동합니다.
- 공기청정기에서는 바람이 나온다.
- 상부 공기 청정기의 바람은 반시계 방향으로 순환하고, 하부 공기 청정기의 바람은 시계 방향으로 순환한다.
- 바람이 불면 미세먼지가 바람 방향으로 모두 1매씩 이동한다.
- 공기청정기로 부는 바람은 미세먼지가 없는 바람이며 공기청정기에 들어간 미세먼지는 모두 정화된다.
- 공기청정기에서는 바람이 나온다.
다음은 확산의 예입니다.
좌우에는 틈이 없기 때문에 양방향으로만 확산이 일어났다.
인접한 4 방향으로 모두 확산이 일어난다.
공기청정기가 있는 매스에서는 확산이 일어나지 않는다.
공기청정기의 바람은 다음 방향으로 순환한다.
방의 정보가 주어졌을 때, T초가 지난 후에 구사과의 방에 남아 있는 미분진의 양을 구해 보자.
입력
첫 번째 행에는 R, C, T(6≤R, C≤50, 1≤T≤1,000)가 주어집니다.
두 번째 행에서 R 행에 $A_{r,c}$(-1 ≤ $A_{r,c}$ ≤ 1,000)이 주어집니다.
공기청정기가 설치되어 있는 것은 $A_{r,c}$가 -1이고, 나머지 값은 미세먼지의 양이다.
-1은 2번 상하에 붙어 있어, 맨 위의 행, 아래의 행과 2개의 칸 이상 떨어져 있다.
출력
첫 번째 행에 T초가 경과한 후 구사과의 방에 남아 있는 미세먼지의 양을 출력한다.
입력 예 1
7 8 1
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0출력 예 1
188미분진의 확산이 일어나면 다음과 같은 상태가 된다.
공기청정기가 작동한 후의 상태는 다음과 같다.
샘플 입력 2
7 8 2
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0출력 예 2
188
입력 예 3
186출력 예 3
186
입력 예 4
7 8 4
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0출력 예 4
178
입력 예 5
7 8 5
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0출력 예 5
172
예제 입력 6
7 8 20
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0출력 예 6
71
입력 예 7
7 8 30
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0출력 예 7
52
입력 예 8
7 8 50
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0출력 예 8
46import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int R;
static int C;
static int T;
static int()() map;
static int airCleaner; // 공기 청정기 밑 행값
static int total; // 총 미세먼지량
static int remove; // 제거한 미세먼지량
private static void spread() { // 미세먼지 확산 메소드
int()() tmpMap = new int(R)(C); // 퍼진 미세먼지 양을 담을 임시 배열
// 상하좌우
int() dx = {-1, 1, 0, 0};
int() dy = {0, 0, -1, 1};
for (int i = 0; i < R; i++) { // 미세먼지 퍼트리기
for (int j = 0; j < C; j++) {
if(map(i)(j) > 4) { // 미세먼지가 있다면(5보다 작은 미세먼지는 확산이 일어나지 않음
int n = map(i)(j) / 5; // 퍼지는 양
for (int k = 0; k < 4; k++) { // 4방을 검사
int nx = i + dx(k);
int ny = j + dy(k);
if(nx >= 0 && nx < R && ny >= 0 && ny < C && map(nx)(ny) > -1) { // 범위 체크 & 공기청정기가 아니라면
tmpMap(nx)(ny) += n; // 퍼진 양을 임시 배열에 담고
map(i)(j) -= n; // 퍼진만큼 양을 줄여줌
}
}
}
}
}
for (int i = 0; i < R; i++) { // 퍼진 양 더해주기
for (int j = 0; j < C; j++) {
if(map(i)(j) > -1) { // 공기청정기의 -1 값을 서로 더해주지 않기 위해
map(i)(j) += tmpMap(i)(j);
}
}
}
}
private static void airCleanerOperation() { // 공기 청정기 작동
// 공기 청정기 위쪽
int top = airCleaner - 1;
remove += map(top - 1)(0); // 제거한 양 더해주고
for (int i = top - 1; i > 0; i--) { // 왼쪽
map(i)(0) = map(i - 1)(0);
}
for (int i = 0; i < C - 1; i++) { // 위쪽
map(0)(i) = map(0)(i + 1);
}
for (int i = 0; i < top; i++) { // 오른쪽
map(i)(C - 1) = map(i + 1)(C - 1);
}
for (int i = C - 1; i > 1; i--) { // 아래쪽
map(top)(i) = map(top)(i - 1);
}
map(top)(1) = 0; // 공기청정기에서 나온 바람 곳은 미세먼지가 없음
// 공기청정기 아래쪽
int bottom = airCleaner;
remove += map(bottom + 1)(0); // 제거한 양 더해주고
for (int i = bottom + 1; i < R - 1; i++) { // 왼쪽
map(i)(0) = map(i + 1)(0);
}
for (int i = 0; i < C - 1; i++) { // 아래쪽
map(R - 1)(i) = map(R - 1)(i + 1);
}
for (int i = R - 1; i > bottom; i--) { // 오른쪽
map(i)(C - 1) = map(i - 1)(C - 1);
}
for (int i = C - 1; i > 1; i--) { // 위쪽
map(bottom)(i) = map(bottom)(i - 1);
}
map(bottom)(1) = 0; // 공기청정기에서 나온 바람 곳은 미세먼지가 없음
}
public static void main(String() args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
T = Integer.parseInt(st.nextToken());
map = new int(R)(C);
for (int i = 0; i < R; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < C; j++) {
map(i)(j) = Integer.parseInt(st.nextToken());
if(map(i)(j) == -1) airCleaner = i;
if(map(i)(j) > 0) total += map(i)(j);
}
}
for (int i = 0; i < T; i++) {
spread(); // 미세먼지 확산
airCleanerOperation(); // 공기청정기 작동
}
// 출력
System.out.println(total - remove);
}
}