[백준] JAVA - 17144. 미세먼지 안녕!

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

17144번: 미세먼지 안녕!

생각

미세먼지의 확산과, 공기청정기가 작동하는 것을 모두 함수로 구현했습니다.

 

1. 미세먼지 확산

우선, 미세먼지의 확산은 모두 동시에 진행되기 때문에 BFS를 사용하여 구현했습니다. 다음으로 확산된 미세먼지들이 누적하는것은 따로 배열에 담아 저장시키고 나서 확산이 끝나면 한번에 누적시켰습니다.

 

미세먼지들이 동시에 확산되고 확산되는 양들을 어떤 타입으로 누적시켜야 할 지 한참 고민하다가 Dust 클래스 타입의 2차원 배열을 선언하여 객체에 접근하여 값을 set하는 방식으로 미세먼지의 양을 계산했는데 오늘 다른 친구들 풀이를 보니 굳이 이렇게 안 해도 된다는것을 알게되었습니다. (이번주 주말내로 다시 풀어보는걸로..)

 

2. 공기청정기 작동

공기청정기의 작동은 단순하게 for문을 4번 돌려서 시계방향과 반시계방향으로 나눠서 각각의 경우마다 모두 처리를 해주었습니다. 이때 회전의 순서가 중요합니다!

공기청정기로 들어가고 나서는 미세먼지가 모두 사라지기 때문에 반드시 회전의 순서를 공기청정기로부터 들어오는 역순으로 구현해야 정답을 출력할 수 있습니다

Java Code

package com.java.algorithm;

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

public class BOJ_17144_미세먼지안녕 {
	static int R,C,T;
	static Dust[][] map;
	static int[] dy = {1,-1,0,0};
	static int[] dx = {0,0,-1,1};
	
	static class Dust{
		int y,x,cnt;

		public Dust(int y, int x, int cnt) {
			super();
			this.y = y;
			this.x = x;
			this.cnt = cnt;
		}
		
		public int getCnt() {
			return cnt;
		}

		public void setCnt(int cnt) {
			this.cnt = cnt;
		}

		@Override
		public String toString() {
			return "Dust [y=" + y + ", x=" + x + ", cnt=" + cnt + "]";
		}
		
	}
	static int cy1=-1,cy2=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());
		
		map = new Dust[R][C];
		
		
		for (int i = 0; i < R; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < C; j++) {
				int dustCnt = Integer.parseInt(st.nextToken());
				map[i][j] = new Dust(i,j,dustCnt);
//				if(dustCnt > 0) {
//					q.add(map[i][j]);
//				}
				if(dustCnt == -1) {
					if(cy1 == -1) {
						cy1 = i;
					}else {
						cy2 = i;
					}
					
				}
			}
		}
		solve();
	}
	public static void solve() {
		int ans = 0;
		for (int t = 0; t < T; t++) {
			//미세먼지 확산
			spread();
			//공기청정기 작동
			clean();
		}
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if(map[i][j].cnt > 0) {
					ans += map[i][j].cnt;
				}
				
			}
		}
		System.out.println(ans);
	}
	
	private static void clean() {
		//위쪽 반시계
		for (int i = cy1-2; i >= 0; i--) {//아래
			map[i+1][0].setCnt(map[i][0].cnt);
		}
		for (int i = 0; i < C-1; i++) {//왼
			map[0][i].setCnt(map[0][i+1].cnt);
		}
		for (int i = 0; i < cy1; i++) {// 위
			map[i][C-1].setCnt(map[i+1][C-1].cnt);
		}
		for (int i = C-2; i >= 0; i--) {//오른
			map[cy1][i+1].setCnt(map[cy1][i].cnt);
		}
		map[cy1][1].setCnt(0);
		
		//아래쪽 시계
		for (int i = cy2+1; i < R-1; i++) {// 위
			map[i][0].setCnt(map[i+1][0].cnt);
		}
		for (int i = 0; i < C-1; i++) {//왼
			map[R-1][i].setCnt(map[R-1][i+1].cnt);
		}
		for (int i = R-2; i >= cy2; i--) {//아래
			map[i+1][C-1].setCnt(map[i][C-1].cnt);
		}
		for (int i = C-2; i >= 0; i--) {//오른
			map[cy2][i+1].setCnt(map[cy2][i].cnt);
		}

		map[cy2][1].setCnt(0);		
//		for (int i = 0; i < R; i++) {
//			for (int j = 0; j < C; j++) {
//				System.out.print(map[i][j].cnt+" ");
//			}
//			System.out.println();
//		}
//		System.out.println();
	}
	
	public static void spread() {
		Queue<Dust> q = new LinkedList<Dust>();
		
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if(map[i][j].cnt > 0) {
					q.add(map[i][j]);
				}
			}
		}
		int[][] spreadTotal = new int[R][C];
		while(!q.isEmpty()) {
			int size = q.size();
			while(size-- > 0){
				Dust now = q.poll();
				int spreadCnt = 0;
				if(now.cnt >= 5) {
					for (int d = 0; d < 4; d++) {
						int ny = now.y + dy[d];
						int nx = now.x + dx[d];
						if(ny >= R || ny < 0 || nx >= C || nx < 0) continue;
						//확산 먼저 시켜준다
						Dust nextDust = map[ny][nx];
						if(nextDust != null && nextDust.cnt != -1) {
							spreadCnt++;
							spreadTotal[ny][nx] += now.cnt/5; // 다음칸에 원래있던값 + 확산되는양
						}
					}
					int remain = now.cnt-(now.cnt/5)*spreadCnt; //미세먼지 누적값 업데이트 
					now.setCnt(remain); // 남은 미세먼지 양 업데이트
				}
				
			} // 확산 끝
			
			// 확산된값 업데이트시켜주기
			for (int i = 0; i < R; i++) {
				for (int j = 0; j < C; j++) {
					Dust now = map[i][j];
					if(now.cnt != -1) {
						now.setCnt(now.cnt+spreadTotal[i][j]);
					}
					
				}
			}
		}
//		for (int i = 0; i < R; i++) {
//			for (int j = 0; j < C; j++) {
//				System.out.print(map[i][j].cnt+" ");
//			}
//			System.out.println();
//		}
//		System.out.println();
	}
}