[알고리즘] Java / 백준 / 미세먼지 안녕! / 17114

[알고리즘] Java / 백준 / 미세먼지 안녕! / 17114

문제

문제 링크

접근 방식

미세먼지를 확산시키는 함수, 공기청정기 작동 함수 두 가지의 기능으로 나누어 구현한다

1. 미세먼지 확산 (한 번 확산)

   • 격자판의 각 값이 1 이상일 경우 Dust 객체(행, 열, 값)를 스택에 보관한다
   • 보관한 스택을 꺼내면서 해당 위치에서 사방탐색 후 확산이 가능한 칸일 경우 확산시킨다
   • 확산한 수치로 현재 미세먼지 값을 수정한다

2. 공기청정기 작동 (한 번 작동)

   • 공기청정기의 위쪽은 반 시계방향으로 탐색하며 이전 위치 값을 현재 위치에 저장한다
   • 공기청정기의 아래쪽은 시계방향으로 한다

3. 미세먼지 확산과 공기청정기 작동을 T 번 반복한 후 먼지의 양을 세어 출력한다

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main_17144 {
	
	static int R,C,T;
	static int[][] mat;
	static int[][] deltas = {{-1,0},{0,1},{1,0},{0,-1}};
	static int[][] airCleaner;
	static int[][] upClear = {{0,1},{-1,0},{0,-1},{1,0}};
	static int[][] downClear = {{0,1},{1,0},{0,-1},{-1,0}};
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		T = Integer.parseInt(st.nextToken());
		
		mat = new int[R][C];
		
		airCleaner = new int[2][2];
		int airIdx = 0;
		for(int i=0;i<R;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<C;j++) {
				mat[i][j] = Integer.parseInt(st.nextToken());
				if(mat[i][j] == -1) airCleaner[airIdx++] = new int[] {i,j};
			}
		}
		
		for(int i=0;i<T;i++) {
			spreadDust();
			airCleanerOn();
		}
		
		
		int cnt =0;
		
		for(int i=0;i<R;i++) {
			for(int j=0;j<C;j++) {
				if(mat[i][j] != -1) cnt += mat[i][j];
			}
		}
		
		System.out.println(cnt);
		
	}
	
	public static class Dust {
		int r,c,a;
		
		Dust(int r, int c, int a){
			this.r = r;
			this.c = c;
			this.a = a;
		}
	}
	
	public static void spreadDust() {
		
		Stack<Dust> dusts = new Stack<>();
		
		
		for(int i=0;i<R;i++) {
			for(int j=0;j<C;j++) {
				if(mat[i][j] > 0) dusts.add(new Dust(i,j,mat[i][j]));
			}
		}
		
		while(!dusts.isEmpty()) {
			Dust dust = dusts.pop();
			
			int spreadCnt = 0;
			for(int i=0;i<4;i++) {
				int nextR = dust.r + deltas[i][0];
				int nextC = dust.c + deltas[i][1];
				
				if(nextR < 0 || nextR >= R || nextC < 0 || nextC >= C || mat[nextR][nextC] == -1) continue;
				spreadCnt++;
				mat[nextR][nextC] += dust.a/5;
			}
			
			mat[dust.r][dust.c] -= dust.a/5 * spreadCnt; 
		}
	}
	
	public static void airCleanerOn() {
		int nowR = airCleaner[0][0];
		int nowC = airCleaner[0][1];
		
		int preValue = 0;
		loop :for(int i=0;i<4;i++) {
			
			while(true) {
				
				int nextR = nowR + upClear[i][0];
				int nextC = nowC + upClear[i][1];
				
				if(nextR < 0 || nextR >= R || nextC < 0 || nextC >= C || mat[nextR][nextC] == -1) continue loop;
				int temp = mat[nextR][nextC];
				mat[nextR][nextC] = preValue;
				preValue = temp;
				
				nowR = nextR;
				nowC = nextC;
			}
		}
		
		nowR = airCleaner[1][0];
		nowC = airCleaner[1][1];
		
		preValue = 0;
		
		loop :for(int i=0;i<4;i++) {
			
			while(true) {
				
				int nextR = nowR + downClear[i][0];
				int nextC = nowC + downClear[i][1];
				
				if(nextR < 0 || nextR >= R || nextC < 0 || nextC >= C || mat[nextR][nextC] == -1) continue loop;
				int temp = mat[nextR][nextC];
				mat[nextR][nextC] = preValue;
				preValue = temp;
				
				nowR = nextR;
				nowC = nextC;
			}
		}
		
	}
}