[백준] 17144번 - 미세먼지 안녕!

문제 >

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

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

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

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

다음은 확산의 예시이다.

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

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

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

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

방의 정보가 주어졌을 때, 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차원 배열 a[r][c]에 저장하고, 1 cycle 마다 두 단계를 거친다. 여기서 1cycle은 1초를 의미한다.

 

1) 미세먼지 확산

 

1 이상인 원소가 상하좌우로 인접한 4개의 원소로 확산된다.

 

인접한 4개의 방향의 원소에 a[i][j] / 5를 저장하고, 확산된 방의 개수만큼 a[i][j]에  a[i][j]/5를 뺀다.

 

이 때, 확산되는 원소의 값이 -1이면 확산이 되지 않는다. 

 

단, 확산을 할 때, 미리 배열의 값을 복사한다. 이유는 1cycle 안에 확산에 의한 확산이 일어나서는 안되기 때문이다.

 

 

2) 공기청정

 

공기청정기은 0열에 존재하고 길이는 세로 2이다.

 

따라서 두 파트로 나누어 원소를 하나씩 밀어준다.

 

예를 들어 공기 청정기가 (x, 0), (x+1, 0) 인덱스에 존재한다면

 

위쪽 공기 청정기는 0에서 x행까지 0에서 c열까지 순환을하고

 

아래쪽 공기 청정기는 x+1에서 r행까지 0에서 c열까지 순환을 한다.

 

위쪽, 아래쪽 각 각 원소값을 하나씩 밀어준다.

 

[JAVA]

package baekjoon;

import java.util.*;

public class BOJ_17144 {
	static int r;
	static int c;
	
	public static void spread(int[][] a) {
		int[] dx = {-1, 0, 1, 0};
		int[] dy = {0, 1, 0, -1};
		
		int[][] b = new int[r][c];
		for(int i = 0; i < r; i++) {
			for(int j = 0; j < c; j++) {
				b[i][j] = a[i][j];
			}
		}
		
		for(int i = 0; i < r; i++) {
			for(int j = 0; j < c; j++) {
				if(b[i][j] >= 0) {
					int cnt = 0;
					for(int k = 0; k < 4; k++) {
						int nx = i + dx[k];
						int ny = j + dy[k];
						
						if(nx >= 0 && ny >= 0 && nx < r && ny < c && a[nx][ny] != -1) {
							a[nx][ny] += b[i][j] / 5;
							cnt++;
						}
					}
					a[i][j] = a[i][j] - (b[i][j]/5) * cnt;
				}
			}
		}
	}
	
	public static void clear(int[][] a, int x, int y, int flag, int[][] d) {
		int bx, tx, ly = 0, ry = c - 1;
		int tmpx = x, tmpy = y;
		int idx = 0;
		if(flag == 0) {
			bx = x;
			tx = 0;
		}
		else {
			bx = r-1;
			tx = x;
		}
		while(true) {
			if(idx > 3) break;
			int nx = tmpx + d[idx][0];
			int ny = tmpy + d[idx][1];
			
			if(nx >= tx && ny >= ly && nx <= bx && ny <= ry) {
				a[tmpx][tmpy] = a[nx][ny];
				tmpx = nx;
				tmpy = ny;
			}
			else idx++;
		}
		a[x][y] = -1;
		a[x][y+1] = 0;
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		r = sc.nextInt();
		c = sc.nextInt();
		int time = sc.nextInt();
		int[] idx = new int[2];
		int[][] up = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
		int[][] down = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
		
		int[][] a = new int[r][c];
		for(int i = 0; i < r; i++) {
			for(int j = 0; j < c; j++) {
				a[i][j] = sc.nextInt();
				if(a[i][j] == -1) {
					idx[0] = i;
					idx[1] = j;
				}
			}
		}
		
		for(int t = 0; t < time; t++) {
			spread(a);
			clear(a, idx[0]-1, idx[1], 0, up);
			clear(a, idx[0], idx[1], 1, down);
		}
		int sum = 0;
		for(int i = 0; i < r; i++) {
			for(int j = 0; j < c; j++) {
				if(a[i][j] == -1) continue;
				sum += a[i][j];
			}
		}
		System.out.println(sum);
	}
}