[백준] 미세먼지 안녕

package com.study.classAlgo;

import java.awt.List;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ17144_미세먼지_안녕 {
	static int N,M,T;
	static int[][] map, temp;
	static Queue<Dust> queue = new LinkedList<>();
	static ArrayList<Integer> machine = new ArrayList<Integer>();   
	static int[] dx = {-1,1,0,0}; //상하좌우
	static int[] dy = {0,0,-1,1};
	// 1. map,temp 생성
	// 2. t초동안 3~4반복
	// 3. 미세먼지 확산
	// - 미세먼지가 있는 모든 칸에서 확산된다. => map은 처음에 미세먼지, temp는 확산 후 결과들만. 동시에 확산되기 때문에 분리해줘서 저장해야한다.
	// - 공기 청정기가 있거나, 칸을 벗어나는지 체크
	// - 확산은 /5이고, 소수점은 버린다. 남은 양도 계산해야한다.
	// 4. 공기청정기 작동
	// 5. 남아있는 미세먼지 양 계산 
	
	static class Dust {
		int x;
		int y;
		
		public Dust(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		T = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		temp = new int[N][M];

		// 1. map 생성
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				temp[i][j] = map[i][j];
				if(map[i][j]>0) queue.offer(new Dust(i,j));//미세먼지들 넣어주기
				if(map[i][j]==-1) machine.add(i);
			}
		}
		
		// 2. t초동안 3~4반복
		for(int tc = 0; tc<T; tc++) {
			spread();
			operate();
			copy();
		}
		
		result();
		
	}
	private static void copy() {
		for(int i=0; i<N; i++) {
			for (int j = 0; j < M; j++) {
				map[i][j] = temp[i][j];
				if(map[i][j]>0) queue.offer(new Dust(i,j));//미세먼지들 넣어주기
			}
		}
		
	}
	private static void result() {
		int r = 0;
		for(int i=0; i<N; i++) {
			for (int j = 0; j < M; j++) {
				//System.out.print(temp[i][j]+" ");
				r += temp[i][j];
			}
			//System.out.println();
		}
		System.out.println(r+2);
	}

	// 4. 공기청정기 작동
	private static void operate() {
		int first = machine.get(0);
		//위: 반시계방향
		//위 -> 아래
		for(int i=first-1; i>0; i--) {
			temp[i][0] = temp[i-1][0];
		}
		
		// 왼<-오
		for(int i=0; i<M-1; i++) {
			temp[0][i] = temp[0][i+1];
		}
		
		// 아래 -> 위
		for(int i=0; i<=first; i++) {
			temp[i][M-1] = temp[i+1][M-1];
		}

		// 왼 -> 오
		for(int i=M-1; i>1; i--) {
			temp[first][i] = temp[first][i-1];
		}
		temp[first][1] = 0;
		
		
		//아래: 시계방향
		first = machine.get(1);
		
		// 아래 -> 위

		for(int i=first+1; i<N-1; i++) {
			temp[i][0] = temp[i+1][0];
		}
		
		// 왼<-오
		for(int i=0; i<M-1; i++) {
			temp[N-1][i] = temp[N-1][i+1];
		}
		
		//위 -> 아래
		for(int i=N-1; i>first; i--) {
			temp[i][M-1] = temp[i-1][M-1];
		}
		// 왼 -> 오
		for(int i=M-1; i>1; i--) {
			temp[first][i] = temp[first][i-1];
		}
		temp[first][1] = 0;

	}

	//범위체크
	private static boolean isValid(int nx, int ny) {
		return (nx>=0 && nx<N && ny>=0 && ny<M) ? true : false;
	}
	
	// 3. 미세먼지 확산
	// - 미세먼지가 있는 모든 칸에서 확산된다. => map은 처음에 미세먼지, temp는 확산 후 결과들만. 동시에 확산되기 때문에 분리해줘서 저장해야한다.
	// - 공기 청정기가 있거나, 칸을 벗어나는지 체크
	// - 확산은 /5이고, 소수점은 버린다. 남은 양도 계산해야한다.
	private static void spread() {
		while(!queue.isEmpty()) {
			Dust d = queue.poll();
			int x = d.x;
			int y = d.y;
			int count = 0;
			int dust = map[x][y] / 5;

			for(int i=0; i<4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				
				if(isValid(nx,ny) && map[nx][ny] != -1) {
					temp[nx][ny] += dust;
					count++;
				}
			}//4방 탐색
			
			//확산된 양에서 빼준다.
			temp[x][y]-= dust * count;
		}		
	}

}