백준 17144 - 미세먼지 안녕!

www.acmicpc.net/problem/17144

17144번: 미세먼지 안녕!

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_BJ_17144_미세먼지안녕 {

							//상, 하, 좌, 우
	private static int[] dy = {0, 0, -1, 1};
	private static int[] dx = {-1, 1, 0, 0};
	private static int R, C, T;
	private static int[][] room;
	private static int[][] cleaner = new int[2][2];
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer tk = new StringTokenizer(br.readLine(), " ");
		R = Integer.parseInt(tk.nextToken());
		C = Integer.parseInt(tk.nextToken());
		T = Integer.parseInt(tk.nextToken());
		
		room = new int[R][C];
		int index = 0;
		
		for(int i = 0; i < R; i++) {
			tk = new StringTokenizer(br.readLine(), " ");
			for(int j = 0; j < C; j++) {
				room[i][j] = Integer.parseInt(tk.nextToken());
				if(room[i][j] == -1) {
					cleaner[index][0] = i;
					cleaner[index][1] = j;
					index++;
				}
			}
		}
		
		for(int i = 0; i < T; i++) {
			// 미세먼지 확산
			spread();
			
//			for(int j = 0; j < R; j++) {
//				System.out.println(Arrays.toString(room[j]));
//			}System.out.println();
			
			
			// 공기청정기 작동
			clear();
//			for(int j = 0; j < R; j++) {
//				System.out.println(Arrays.toString(room[j]));
//			}System.out.println();
		}
		
		int result = countDust();
		
		System.out.println(result);
	}
	
	public static void spread() {
		Queue<int[]> que = new ArrayDeque<int[]>();
		int[][] curRoom = new int[R][C];
		
		for(int i = 0; i < R; i++) {
			for(int j = 0; j < C; j++) {
				if(room[i][j] > 0) que.add(new int[] {i, j});
			}
		}
		
		while(!que.isEmpty()) {
			int[] cur = que.poll();
			int curDust = room[cur[0]][cur[1]];
			int spreadDust = (int)curDust/5;
			
			for(int i = 0; i < 4; i++) {
				int cx = cur[0] + dx[i];
				int cy = cur[1] + dy[i];
				
				if(cx >= 0 && cy >= 0 && cx < R && cy < C && room[cx][cy] >= 0) {
					curRoom[cx][cy] += spreadDust;
					curDust -= spreadDust;
				}
			}
			
			room[cur[0]][cur[1]] = curDust;
		}
		
		for(int i = 0; i < R; i++) {
			for(int j = 0; j < C; j++) {
				room[i][j] += curRoom[i][j];
			}
		}
		
	}
	
	public static void clear() {
		int height = cleaner[0][0];
		
		for(int k = 1; k < height; k++)	room[height-k][0] = room[height-k-1][0];
		for(int k = 0; k < C-1; k++) 	room[0][k] = room[0][k+1];
		for(int k = 0; k < height; k++)	room[k][C-1] = room[k+1][C-1];
		for(int k = 0; k < C-1; k++)	room[height][C-1-k] = room[height][C-1-k-1];
		room[height][1] = 0;
		
		height = cleaner[1][0];
		
		for(int k = 1; k < R - height-1; k++)	room[height+k][0] = room[height+k+1][0];
		for(int k = 0; k < C-1; k++) 		room[R-1][k] = room[R-1][k+1];
		for(int k = 0; k < R - height-1; k++)	room[R-1-k][C-1] = room[R-1-k-1][C-1];
		for(int k = 0; k < C-1; k++)		room[height][C-1-k] = room[height][C-1-k-1];
		room[height][1] = 0;
	}
	
	public static int countDust() {
		int res = 0;
		
		for(int i = 0; i < R; i++) {
			for(int j = 0; j < C; j++) {
				if(room[i][j] > -1)	res += room[i][j];
			}
		}
		
		return res;
	}

}