1. 문제
설명
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.
공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.
1초 동안 아래 적힌 일이 순서대로 일어난다.
- 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
- (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
- 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
- 확산되는 양은 Ar,c/5이고 소수점은 버린다.
- (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.
- 공기청정기가 작동한다.
- 공기청정기에서는 바람이 나온다.
- 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
- 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
- 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.
다음은 확산의 예시이다.
왼쪽과 오른쪽에 칸이 없기 때문에, 두 방향으로만 확산이 일어났다.
인접한 네 방향으로 모두 확산이 일어난다.
공기청정기가 있는 칸으로는 확산이 일어나지 않는다.
공기청정기의 바람은 다음과 같은 방향으로 순환한다.
방의 정보가 주어졌을 때, 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초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.
2. 풀이
단순 시뮬레이션 문제입니다.
핵심 구현 파트는 미세먼지의 확산과 공기 청정기의 정화 작용입니다.
하나씩 계획을 세우며 살펴봅시다.
계획1 - 미세먼지 좌표와 확산량을 큐에 넣습니다.
// 계획 1 - 미세먼지 좌표와 확산량을 큐에 넣습니다.
for (int y = 0; y < R; y++) {
for (int x = 0; x < C; x++) {
if (room[y][x] > 0) {
q.add(new int[] {y, x, (int) Math.floor(room[y][x] / 5)});
}
}
}확산될 수 있는 미세먼지 좌표를 먼저 다 기억을 해놓아야
각 미세먼지에 대해 한 번씩만 확산시킬 수 있습니다.
만약 큐에 넣지 않고 바로바로 먼지를 확산시켰다면
확산된 먼지가 또 다른 먼지를 확산시켜버려서 틀리게 됩니다.
계획2 - 미세먼지를 퍼뜨립니다.
while (!q.isEmpty()) {
int[] dust = q.poll();
int y = dust[0];
int x = dust[1];
int diffuse = dust[2];
for (int dir = 0; dir < 4; dir++) {
int ny = y + my[dir];
int nx = x + mx[dir];
if (isOutOfRange(ny, nx)) continue;
if (room[ny][nx] == -1) continue;
room[ny][nx] += diffuse;
room[y][x] -= diffuse;
}
}큐에 저장된 미세먼지 좌표와 확산량의 정보로
인접한 4방향에 대해 퍼뜨립니다.
이 때 공기청정기 좌표일 땐 넘어갑니다.
계획3 - 공기 청정기를 가동합니다.
static void purify(int cleanerY, int[] my) {
int y = cleanerY + my[0];
int x = 0;
// 4방향에 대해 이동
for (int dir = 0; dir < 4; dir++) {
while (true) {
int ny = y + my[dir];
int nx = x + mx[dir];
if (isOutOfRange(ny, nx)) break;
if (room[ny][nx] == -1) break;
room[y][x] = room[ny][nx];
y = ny;
x = nx;
// 맨 끝에 다달았을 때, 공기 청정기의 라인이라면 방향을 꺽어줍니다.
if (x == C - 1 && y == cleanerY) break;
}
}
room[y][x] = 0;
}3. 전체 코드
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static int R, C, T;
static int[][] room;
static int[] my = {-1, 0, 1, 0};
static int[] mx = {0, 1, 0, -1};
static int[] bottomCleanerY = {1, 0, -1, 0};
// 공기 정화 메서드
static void purify(int cleanerY, int[] my) {
int y = cleanerY + my[0];
int x = 0;
for (int dir = 0; dir < 4; dir++) {
while (true) {
int ny = y + my[dir];
int nx = x + mx[dir];
if (isOutOfRange(ny, nx)) break;
if (room[ny][nx] == -1) break;
room[y][x] = room[ny][nx];
y = ny;
x = nx;
if (x == C - 1 && y == cleanerY) break;
}
}
room[y][x] = 0;
}
static boolean isOutOfRange(int y, int x) {
return y < 0 || y >= R || x < 0 || x >= C;
}
public static void main(String[] args) throws Exception {
StringTokenizer stk = new StringTokenizer(br.readLine());
R = Integer.parseInt(stk.nextToken());
C = Integer.parseInt(stk.nextToken());
T = Integer.parseInt(stk.nextToken());
Queue<int[]> q = new LinkedList<>();
room = new int[R][C];
int[] airCleaner = new int[2];
int cleanerIdx = 0;
for (int i = 0; i < R; i++) {
stk = new StringTokenizer(br.readLine());
for (int j = 0; j < C; j++) {
room[i][j] = Integer.parseInt(stk.nextToken());
if (room[i][j] == -1) {
airCleaner[cleanerIdx++] = i;
}
}
}
for (int t = 0; t < T; t++) {
// 계획1 - 미세먼지 좌표와 확산량을 큐에 넣습니다.
for (int y = 0; y < R; y++) {
for (int x = 0; x < C; x++) {
if (room[y][x] > 0) {
q.add(new int[] {y, x, (int) Math.floor(room[y][x] / 5)});
}
}
}
// 계획2 - 미세먼지를 퍼뜨립니다.
while (!q.isEmpty()) {
int[] dust = q.poll();
int y = dust[0];
int x = dust[1];
int diffuse = dust[2];
for (int dir = 0; dir < 4; dir++) {
int ny = y + my[dir];
int nx = x + mx[dir];
if (isOutOfRange(ny, nx)) continue;
if (room[ny][nx] == -1) continue;
room[ny][nx] += diffuse;
room[y][x] -= diffuse;
}
}
// 걔획3 - 공기 청정기를 가동합니다.
purify(airCleaner[0], my);
purify(airCleaner[1], bottomCleanerY);
}
// 계획4 - 남은 미세먼지를 셉니다.
int ans = 0;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
ans += room[i][j];
}
}
bw.write(ans + 2 + "");
bw.close();
}
}
