문제
문제 설명
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.
공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.
1초 동안 아래 적힌 일이 순서대로 일어난다.
- 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
- (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
- 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
- 확산되는 양은 A/5이고 소수점은 버린다. 즉, ⌊A/5⌋이다. r,c r,c
- (r, c)에 남은 미세먼지의 양은 A - ⌊A/5⌋×(확산된 방향의 개수) 이다. r,c r,c
- 공기청정기가 작동한다.
- 공기청정기에서는 바람이 나온다.
- 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
- 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
- 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.
다음은 확산의 예시이다.
왼쪽과 위쪽에 칸이 없기 때문에, 두 방향으로만 확산이 일어났다.
인접한 네 방향으로 모두 확산이 일어난다.
공기청정기가 있는 칸으로는 확산이 일어나지 않는다.
공기청정기의 바람은 다음과 같은 방향으로 순환한다.
방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.
제한 사항
입출력 예
| 입력 | 출력 |
|---|---|
| 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 | 188 |
| 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 | 188 |
| 7 8 3 | |
| 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 | 186 |
| 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 | 178 |
| 7 8 5 | |
| 0 0 0 0 0 0 0 | |
| 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 | 172 |
| 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 | 71 |
| 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 | 52 |
입출력 예 설명
아이디어
제출 코드
import java.io.*;
import java.util.StringTokenizer;
public class four17144 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static StringBuilder sb = new StringBuilder();
static StringTokenizer st;
static int colNum;
static int rowNum;
static int time;
static int[][] map;
// 우 하 상 좌
static int[] dCol = new int[]{1, 0, 0, -1};
static int[] dRow = new int[]{0, -1, 1, 0};
static int[][] cleaner = new int[2][2];
public void solution() throws IOException {
int count = 0;
st = new StringTokenizer(br.readLine());
rowNum = Integer.parseInt(st.nextToken());
colNum = Integer.parseInt(st.nextToken());
time = Integer.parseInt(st.nextToken());
map = new int[rowNum][colNum];
for (int i = 0; i < rowNum; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < colNum; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if (map[i][j] == -1) {
cleaner[count][0] = i;
cleaner[count][1] = j;
count++;
}
}
}
while (time > 0) {
spread();
freshOne();
freshTwo();
time--;
}
count = 0;
for (int i = 0; i < rowNum; i++) {
for (int j = 0; j < colNum; j++) {
if (map[i][j] > 0) count += map[i][j];
}
}
sb.append(count);
bw.write(sb.toString());
bw.flush();
}
// 상 좌 하 우
private void freshTwo() {
int[] spotTwo = cleaner[1];
for (int i = spotTwo[0] + 1; i < rowNum - 1; i++) {
map[i][0] = map[i + 1][0];
}
for (int i = 0; i < colNum - 1; i++) {
map[rowNum - 1][i] = map[rowNum - 1][i + 1];
}
for (int i = rowNum - 1; i > spotTwo[0]; i--) {
map[i][colNum - 1] = map[i - 1][colNum - 1];
}
for (int i = colNum - 1; i > 0; i--) {
map[spotTwo[0]][i] = map[spotTwo[0]][i - 1];
}
map[spotTwo[0]][1] = 0;
}
// 하 좌 상 우
private void freshOne() {
int[] spotOne = cleaner[0];
for (int i = spotOne[0] - 1; i > 0; i--) {
map[i][0] = map[i - 1][0];
}
for (int i = 0; i < colNum - 1; i++) {
map[0][i] = map[0][i + 1];
}
for (int i = 0; i < spotOne[0]; i++) {
map[i][colNum - 1] = map[i + 1][colNum - 1];
}
for (int i = colNum - 1; i > 0; i--) {
map[spotOne[0]][i] = map[spotOne[0]][i - 1];
}
map[spotOne[0]][1] = 0;
}
private void spread() {
int[][] temp = new int[rowNum][colNum];
for (int i = 0; i < rowNum; i++) {
for (int j = 0; j < colNum; j++) {
temp[i][j] = map[i][j];
}
}
for (int i = 0; i < rowNum; i++) {
for (int j = 0; j < colNum; j++) {
if (map[i][j] > 0) {
int spreadAmount = temp[i][j] / 5;
if (spreadAmount == 0) continue;
int spreadCnt = 0;
// (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산
for (int d = 0; d < 4; d++) {
int nextRow = i + dRow[d];
int nextCol = j + dCol[d];
// 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않음
if (nextRow < 0 || nextRow >= rowNum || nextCol < 0 || nextCol >= colNum) continue;
if (map[nextRow][nextCol] == -1) continue;
map[nextRow][nextCol] = map[nextRow][nextCol] + spreadAmount;
spreadCnt++;
}
map[i][j] = map[i][j] - spreadAmount * spreadCnt;
}
}
}
}
public static void main(String[] args) throws IOException {
new four17144().solution();
}
}