백준17144 - 미세먼지안녕 java풀이

package a0225;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

/* 
 
 먼지 나눠주는 과정에서 양이 중복되지 않도록 조심해야함 
 -> 같은 단계인데 더해진 값으로 계산하면 더 많이 나눠줄수있음 주의
 
 *** 나눠줄떄 ***
 큐에 들어있는 기준값으로 조건에 맞는 사방으로 나눠줌
 더해줄때 좌표의 값 + 나눠줄값 으로 계산
 
 *** 나눠주고 남은값계산 *** 
 (큐에 들어있는 기준값 - 총 나눠준값) -> 이렇게 하면 안됨
 
 why?	-> 	다른곳에서 현재 좌표에 먼지를 나눠줘서 기존 먼지양보다 늘어났을수도 있음 
 따라서 나눠주는값은 기존의 큐값을 기준으로 나눠주되 빼줄때는 현재 좌표의 값에서 나눠준값을 빼준다. 
 
 
 *** 초마다 계산을 하므로 큐에 값을 또 넣지 않는다. ***
 */


public class 백준17144_미세먼지안녕 {
	
	static int sero ;
	static int garo ;
	static int time ;
	static int[][] arr ;
	static int[][] visit;
	
	static int[] di = {-1, 0, 1, 0};
	static int[] dj = {0, 1, 0, -1};
	
	static boolean check(int i, int j) {
		if(0<=i&&i<sero && 0<=j&&j<garo)return true;
		return false;
	}
	
	static void spread() {
		Queue<int[]>q = new LinkedList<int[]>();
		
		for(int i=0; i<sero; i++) {							//먼지 입력 
			for(int j=0; j<garo; j++) {
				if(arr[i][j]!=0 && arr[i][j]!=-1)q.add(new int[] {i,j,arr[i][j]});	// 좌표, 그좌표에 있는 먼지양
			}
		}
		
		while(!q.isEmpty()) {
			int now[] = q.poll();
			int nowi = now[0]; int nowj = now[1]; int stddust = now[2];
			
			ArrayList<int[]> cango = new ArrayList<>();		//사방탐색에서 가능한곳의 좌표 리스트
			
			for(int d=0; d<4; d++) {
				int ni = nowi+di[d];
				int nj = nowj+dj[d];
				if(check(ni, nj) && arr[ni][nj]!=-1)cango.add(new int[] {ni, nj});
			}
			if(cango.size()==0)continue;			//나눠줄수있는곳이 없다면 다음으로
			
			int divdust = stddust/5;				// 사방에 각각 나눠줄 먼지의 양 
			if(divdust == 0)continue; 				//나눠줄수있는게 없으면 다음으로
			
			for(int i=0; i<cango.size(); i++) {
				int[] can = cango.get(i);
				int cani = can[0]; int canj = can[1];
				arr[cani][canj]+=divdust;			//사방으로 먼지 나눠주기
			}
			arr[nowi][nowj]-=(cango.size()*divdust);
		}
		
	}
	
	static boolean check(int i, int j, int stdi) {
		if(0<=i&&i<=stdi && 0<=j&&j<garo)return true;
		return false;
	}
	
	static boolean check2(int i, int j, int stdi) {
		if(stdi<=i&&i<sero && 0<=j&&j<garo)return true;
		return false;
	}
	
	static void aircondition(int firstidx) {
		int air1i = firstidx; int air1j = 0;
		int air2i = firstidx+1; int air2j = 0;
		
		
		int[] di= {-1, 0, 1, 0};		//옮길좌표를 찾는과정,	상,우,하,좌 
		int[] dj= {0, 1, 0, -1};
		int d = 0;
		
		int nowi = air1i; int nowj = air1j;
		
		while(true) {		
			
			int ni = nowi+di[d]; int nj = nowj+dj[d];
			//System.out.println("nowi:"+nowi+" nowj:"+nowj+" ni:"+ni+" nj:"+nj);
			if(ni==air1i && nj==air1j) {
				arr[nowi][nowj] = 0;
				break;
			}
			
			if(check(ni, nj, air1i)) {
				arr[nowi][nowj] = arr[ni][nj];
				nowi = ni; nowj = nj;
			}else {
				d = (d+1)%4;
			}
		}
		arr[air1i][air1j] = -1;
		
		int[] d2i = {1, 0, -1, 0};		//옮길좌표 찾는과정,  하,우,상,좌
		int[] d2j = {0, 1, 0, -1};
		d = 0;
		
		nowi = air2i; nowj=air2j;
		
		while(true) {
			int ni = nowi+d2i[d]; int nj = nowj+d2j[d];
			if(ni==air2i && nj==air2j) {
				arr[nowi][nowj] = 0;
				break;
			}
			
			if(check2(ni, nj, air2i)) {
				arr[nowi][nowj] = arr[ni][nj];
				nowi = ni; nowj = nj;
			}else {
				d = (d+1)%4;
			}
		}
		arr[air2i][air2j] = -1;
	}
	
	static void print() {
		for(int i=0; i<sero; i++) {
			for(int j=0; j<garo; j++) {
				System.out.print(arr[i][j]+" ");
			}
			System.out.println();
		}
	}
	
	static int cal() {
		
		int sum = 0;
		for(int i=0; i<sero; i++) {
			for(int j=0; j<garo; j++) {
				if(arr[i][j]!=-1)sum+=arr[i][j];
			}
		}
		return sum;
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer ST =new StringTokenizer(br.readLine());
		
		sero = Integer.parseInt(ST.nextToken());
		garo = Integer.parseInt(ST.nextToken());
		time = Integer.parseInt(ST.nextToken());
		
		arr = new int[sero][garo];
		int airconidx = -1;
		
		for(int i=0; i<sero; i++) {							//입력
			ST = new StringTokenizer(br.readLine());
			for(int j=0; j<garo; j++) {
				arr[i][j] = Integer.parseInt(ST.nextToken());
				if(arr[i][j]==-1 && airconidx==-1)airconidx=i;	//공기청정기의 첫 idx
			}
		}
		//print();
		
		for(int i=0; i<time; i++) {
			spread();
			//print();
			//System.out.println();
			
			aircondition(airconidx);
			//print();
			//System.out.println();
		}
		
		System.out.println(cal());
	}

}