문제
R x C 격자에 미세먼지와 공기청정기가 있다. T초 동안 매초 미세먼지 확산과 공기청정기 순환이 일어날 때, 남은 미세먼지의 총량을 구하라.
입력
첫째 줄에 R, C, T가 주어진다. 이후 R줄에 격자 상태가 주어진다 (-1: 공기청정기, 0 이상: 미세먼지 양).
출력
T초 후 남은 미세먼지 총량을 출력한다.
예제
| 입력 | 출력 |
|---|---|
7 8 1 0 0 0 0 0 0 0 9 0 0 0 0 3 0 0 8 -1 0 5 2 0 0 0 2 -1 8 5 3 0 0 0 5 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 112 |
풀이
매 초 (1) 미세먼지 확산, (2) 공기청정기 순환을 반복한다.
- 확산: 각 칸의 미세먼지가 4방향으로 1/5씩 퍼진다 (공기청정기, 범위 밖 제외). 새 배열에 누적한다
- 순환: 공기청정기 위쪽은 반시계 방향, 아래쪽은 시계 방향으로 한 칸씩 밀린다. 공기청정기에서 나오는 바람은 미세먼지 0이다
- T회 반복 후 격자의 양수 값 합계를 출력한다
핵심 아이디어: 확산은 동시에 일어나므로 새 배열에 누적하고, 순환은 배열의 경계를 따라 값을 한 칸씩 시프트하여 구현한다.
코드
package ASP_study.day299;
import java.io.*;
import java.util.*;
public class Day281BOJ17144공청기구현 {
static int R, C, T; // 행
static int[][] map;
static class Machine {
int upX, upY;
int downX, downY;
public Machine(int upX, int upY, int downX, int downY) {
super();
this.upX = upX;
this.upY = upY;
this.downX = downX;
this.downY = downY;
}
}
static Machine machine;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer 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];
boolean isMachine = false;
machine = null;
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 && !isMachine) { // (0,0) ~ (R,C) 위에서부터 검사하므로 downX는 +1
machine = new Machine(i, j, i + 1, j);
map[i + 1][j] = -1;
isMachine = true;
}
}
}
for (int t = 1; t <= T; t++) {
map = dust();
cleaner();
}
int ans = 0;
for (int[] ma : map) {
for (int m : ma) {
if (m > 0)
ans += m;
}
}
System.out.println(ans);
}
public static int[][] dust() {
int[] dr = { -1, 0, 1, 0 };
int[] dc = { 0, 1, 0, -1 };
int[][] newmap = new int[R][C];
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (map[i][j] > 0) {
int res = map[i][j] / 5;
int cnt = 0;
for (int d = 0; d < 4; d++) {
int nx = i + dr[d];
int ny = j + dc[d];
if (nx < 0 || nx >= R || ny < 0 || ny >= C || map[nx][ny] == -1)
continue;
if (nx >= 0 && nx < R && ny >= 0 && ny < C && map[nx][ny] != -1) {
cnt++;
newmap[nx][ny] += res;
}
}
newmap[i][j] += map[i][j] - (cnt * res);
}
}
}
newmap[machine.upX][machine.upY] = -1;
newmap[machine.downX][machine.downY] = -1;
return newmap;
}
public static void cleaner() {
windUp();
windDown();
}
public static void windUp() {
int x = machine.upX;
int y = machine.upY;
int[] dr = { -1, 0, 1, 0 };
int[] dc = { 0, 1, 0, -1 };
for (int d = 0; d < 4; d++) {
while (true) {
int nx = x + dr[d];
int ny = y + dc[d];
if (nx >= 0 && nx <= machine.upX && ny >= 0 && ny <= C - 1) {
map[x][y] = map[nx][ny];
x = nx;
y = ny;
} else {
break;
}
}
}
map[machine.upX][machine.upY] = -1;
map[machine.upX][machine.upY + 1] = 0;
}
public static void windDown() {
int sx = machine.downX;
int sy = machine.downY;
int[] dr = { 1, 0, -1, 0 };
int[] dc = { 0, 1, 0, -1 };
for (int d = 0; d < 4; d++) {
while (true) {
int nx = sx + dr[d];
int ny = sy + dc[d];
if (nx >= machine.downX && nx <= R - 1 && ny >= 0 && ny <= C - 1) {
map[sx][sy] = map[nx][ny];
sx = nx;
sy = ny;
} else {
break;
}
}
}
map[machine.downX][machine.downY] = -1;
map[machine.downX][machine.downY + 1] = 0;
}
}복잡도
- 시간: O(T * R * C)
- 공간: O(R * C)