백준 17144 미세먼지 안녕!

https://www.acmicpc.net/problem/17144

17144번: 미세먼지 안녕!

* 확산

1.확산배열 => 확산값만 따로 누적 저장

2. 먼지가있는칸은 따로 갱신

3.기존맵+확산배열 더해주기

 

for(모든칸에 대해)

if(숫자)->list.add(좌표)

 

for(list)

4방탐색

범위안and -1(공기청정기)이 아니면 -> 확산배열갱신

endfor

 

먼지있던칸 값 갱신

맵+확산맵 더해주기.

 

*airClean

1.배열돌면서 큐에 배열값하니씩 넣기

2. 배열돌면서 큐에서빼서 1개씩 넣어주기.

3. 공기청정기오른쪽값=0으로.

while(True)

범위밖이면 방향전환

공기청정기만남->break

 

*main

for(T번만큼)

확산

공기청정

확산배열 초기화

endfor

미세먼지 세기==정답

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

public class Main_17144_유동훈 {

	static int R;
	static int C;
	static int T;
	static int[][] origin;
	static int[][] map;
	static int[][] spread;
	static int[] dr= {-1,1,0,0};
	static int[] dc= {0,0,-1,1};
	
	//오,위,왼,아
	static int[] dr1= {0,-1,0,1};
	static int[] dc1= {1,0,-1,0};
	
	//오,아,왼,위
	static int[] dr2= {0,1,0,-1};
	static int[] dc2= {1,0,-1,0};
	static List<int[]> airClean;
	
	static void copyArr()
	{
		for(int i=0;i<R;++i)
		{
			//st=new StringTokenizer(br.readLine());
			for(int j=0;j<C;++j)
			{
				map[i][j]=origin[i][j];
			}
		}
	}
	
	static void copyArr2()
	{
		for(int i=0;i<R;++i)
		{
			//st=new StringTokenizer(br.readLine());
			for(int j=0;j<C;++j)
			{
				origin[i][j]=map[i][j];
			}
		}
	}
	
	static void print()
	{
		System.out.println("===================");
		for(int i=0;i<R;++i)
		{
			//st=new StringTokenizer(br.readLine());
			for(int j=0;j<C;++j)
			{
				System.out.print(map[i][j]+" ");
			}
			System.out.println();
		}
	}
	
	static void spread()
	{
		List<int[]> list= new ArrayList<>();
		for(int i=0;i<R;++i)
		{
			//st=new StringTokenizer(br.readLine());
			for(int j=0;j<C;++j)
			{
				if(map[i][j]!=0 && map[i][j]!=-1)
				{
					list.add(new int[] {i,j});
				}
			}
		}
		
		//모든 먼지가있는 칸에 대해
		//확산배열에 확산값 누적 저장
		for(int[] item:list)
		{
			int spreadCount=0;
			for(int i=0;i<4;++i)
			{
				int nr=item[0]+dr[i];
				int nc=item[1]+dc[i];
				
				if(nr>=0 && nr<R && nc>=0 && nc<C)
				{
					if(map[nr][nc]!=-1)
					{
						//System.out.println(item[0]+" "+item[1]);
						spread[nr][nc]=spread[nr][nc]+map[item[0]][item[1]]/5;
						spreadCount++;
					}
				}
			}
			//미세먼지가 있던칸 갱신
			map[item[0]][item[1]]=map[item[0]][item[1]]-(map[item[0]][item[1]]/5)*spreadCount;
			//print();
		}
		//copyArr2();
		
		//기존맵에 확산된 먼지 더하기
		for(int i=0;i<R;++i)
		{
			//st=new StringTokenizer(br.readLine());
			for(int j=0;j<C;++j)
			{
				map[i][j]=map[i][j]+spread[i][j];
			}
			//System.out.println();
		}
	}
	
	static void airClean1()
	{
		Queue<Integer> q= new LinkedList<>();
		
		//방향전환 인덱스
		int cur=0;
		
		int nr=airClean.get(0)[0];
		int nc=airClean.get(0)[1];
			
		
		while(true)
		{
			nr=nr+dr1[cur];
			nc=nc+dc1[cur];
			
			//범위밖이면 방향전환
			if(nr<0 || nr>=R || nc<0 || nc>=C)
			{
				if(nr<0) nr=nr+1;
				if(nr>=R) nr=nr-1;
				if(nc<0) nc=nc+1;
				if(nc>=C) nc=nc-1;
				cur=(cur+1)%4;
				//System.out.println("nr:"+nr+"nc:"+nc);
				//System.out.println("방향전환"+cur);
				continue;
				
			}
			
			
			//범위안
			//공기청정기만나면 그만해
			if(map[nr][nc]==-1)
			{
				break;
			}
			
			//범위안이면
			//System.out.println(nr+" "+nc);
			//System.out.println(map[nr][nc]);
			q.add(map[nr][nc]);
			
			//print();
		}
		
		cur=0;
		
		//System.out.println("바람시작");
		nr=airClean.get(0)[0];
		nc=airClean.get(0)[1]+1; //한칸땡겨	
		//큐에있는것을 하나씩 넣어주기
		while(true)
		{
			
			nr=nr+dr1[cur];
			nc=nc+dc1[cur]; 	
			
			//범위밖이면 방향전환
			if(nr<0 || nr>=R || nc<0 || nc>=C)
			{
				cur=(cur+1)%4;
				
				//값 보정
				if(nr<0) nr=nr+1;
				if(nr>=R) nr=nr-1;
				if(nc<0) nc=nc+1;
				if(nc>=C) nc=nc-1;
				continue;
			}
			
			//System.out.println();
			//System.out.println("디버깅:"+map[nr][nc]);
			//범위안이면
			//공기청정기이면 그만
			if(map[nr][nc]==-1)
			{
				break;
			}
			//공기청정기 아니면 값대입
			else
			{
				//System.out.println(nr+" "+nc);
				map[nr][nc]=q.poll();
				//System.out.println(map[nr][nc]);
			}
			
			//print();	
		}
		//print();
		//int nr=airClean.get(0)[0]+dr1[i];
		//오른쪽칸 0으로
		map[airClean.get(0)[0]][airClean.get(0)[1]+1]=0;
	}
	
	//아래쪽 공기청정기
	static void airClean2()
	{
		Queue<Integer> q= new LinkedList<>();
		
		//방향전환 인덱스
		int cur=0;
		
		int nr=airClean.get(1)[0];
		int nc=airClean.get(1)[1];
			
		
		while(true)
		{
			nr=nr+dr2[cur];
			nc=nc+dc2[cur];
			
			//범위밖이면 방향전환
			if(nr<0 || nr>=R || nc<0 || nc>=C)
			{
				if(nr<0) nr=nr+1;
				if(nr>=R) nr=nr-1;
				if(nc<0) nc=nc+1;
				if(nc>=C) nc=nc-1;
				cur=(cur+1)%4;
				//System.out.println("nr:"+nr+"nc:"+nc);
				//System.out.println("방향전환"+cur);
				continue;
				
			}
			
			
			//범위안
			//공기청정기만나면 그만해
			if(map[nr][nc]==-1)
			{
				break;
			}
			
			//범위안이면
			//System.out.println(nr+" "+nc);
			//System.out.println(map[nr][nc]);
			q.add(map[nr][nc]);
			
			//print();
		}
		
		cur=0;
		
		//System.out.println("바람시작");
		nr=airClean.get(1)[0];
		nc=airClean.get(1)[1]+1; //한칸땡겨	
		//큐에있는것을 하나씩 넣어주기
		while(true)
		{
			
			nr=nr+dr2[cur];
			nc=nc+dc2[cur]; 	
			
			//범위밖이면 방향전환
			if(nr<0 || nr>=R || nc<0 || nc>=C)
			{
				cur=(cur+1)%4;
				
				//값 보정
				if(nr<0) nr=nr+1;
				if(nr>=R) nr=nr-1;
				if(nc<0) nc=nc+1;
				if(nc>=C) nc=nc-1;
				continue;
			}
			
			//System.out.println();
			//System.out.println("디버깅:"+map[nr][nc]);
			//범위안이면
			//공기청정기이면 그만
			if(map[nr][nc]==-1)
			{
				break;
			}
			//공기청정기 아니면 값대입
			else
			{
				//System.out.println(nr+" "+nc);
				map[nr][nc]=q.poll();
				//System.out.println(map[nr][nc]);
			}
			
			//print();	
		}
		//print();
		//int nr=airClean.get(0)[0]+dr1[i];
		//오른쪽칸 0으로
		map[airClean.get(1)[0]][airClean.get(1)[1]+1]=0;
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		//StringBuilder sb=new StringBuilder();
		StringTokenizer st;
		st=new StringTokenizer(br.readLine());
		R=Integer.parseInt(st.nextToken());
		C=Integer.parseInt(st.nextToken());
		T=Integer.parseInt(st.nextToken());
		
		//origin=new int[R][C];
		map=new int[R][C];
		spread=new int[R][C];
		
		airClean= new ArrayList<>();
		for(int i=0;i<R;++i)
		{
			st=new StringTokenizer(br.readLine());
			for(int j=0;j<C;++j)
			{
				map[i][j]=Integer.parseInt(st.nextToken());
				if(map[i][j]==-1)
				{
					airClean.add(new int[] {i,j});
				}
			}
		}
		
		//---------------------입력 끝-------------------------
		for(int i=0;i<T;++i)
		{
			//copyArr();
			spread();
			airClean1();
			airClean2();
			
			//확산배열초기화
			for(int a=0;a<R;++a)
			{
				for(int j=0;j<C;++j)
				{
					spread[a][j]=0;
							
				}
			}
			//print();
		}
		
		//미세먼지 세기
		int sum=0;
		for(int i=0;i<R;++i)
		{
			for(int j=0;j<C;++j)
			{
				if(map[i][j]!=0 && map[i][j]!=-1)
					sum=sum+map[i][j];
						
			}
		}
		
		System.out.println(sum);
	}
	

}