[ 백준 / BOJ 17144 ] 미세먼지 안녕! ( JAVA )

문제 설명

공기청정기 ➡️ 1번 열에 설치, 두 행을 차지함
$A_{r,c}$ : (r,c)에 있는 미세먼지의 양


1초 동안 발생하는 일

1. 미세 먼지 확산 (모두 동시에 발생)
   • (r,c)에 있는 미세먼지는 인접한 네 방향으로 확산
   • 인접한 방향에 공기청정기가 있거나, 범위가 벗어나면 확산❎
   • 확산 되는 양 : $A_{r,c}$/5, 소수점은 버림
   • (r,c)에 남는 양 : $A_{r,c} - (A_{r,c}/5)$x(확산된 방향의 개수)
2. 공기정청기 작동
   • 위쪽 바람은 반시계방향 순환, 아래쪽 바람은 시계방향으로 순환
   • 미세먼지는 바람 방향대로 한 칸씩 이동
   • 공기청정기로 들어간 미세먼지는 정화

T초 후, 남은 미세먼지의 양⁇

문제 풀이

순서대로 진행하면 된다‼

fineDust(int x, int y, int amout) 👉 미세먼지 정보 객체
amountOfFineDust[i][j] : (i,j)의 미세먼지 양
airCleaner : 공기 청정기의 윗 행 값

1. 미세먼지 위치 확인 & 확산

1) checkDust() : 미세먼지를 dusts에 추가
2) spreadDust() : 미세먼지 확산
- (i,j의 미세먼지 양 < 5라면 확산하지 않는다.
- 공기청정기가 아니고, 범위가 벗어나지 않는 각 네 방향으로 now.amount/5 를 추가
- (i,j)의 미세먼지 양 -= (amountOfSpread * cnt)

2. 공기청정기 작동

operateAirCleaner()

간단하게 구현~!
바람 방향으로 이동시켜주면 된다!
공기청정기로 들어오면 정화

코드

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 Main_BOJ_17144_미세먼지_안녕 {
    static int R, C, T;
    static int airCleaner = -1;
    static int[][] amountOfFineDust;
    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, -1, 1, 0};
    static Queue<fineDust> dusts;

    static class fineDust {
        int x;
        int y;
        int amount;

        public fineDust(int x, int y, int amount) {
            this.x = x;
            this.y = y;
            this.amount = amount;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());

        R = Integer.parseInt(stringTokenizer.nextToken());
        C = Integer.parseInt(stringTokenizer.nextToken());
        T = Integer.parseInt(stringTokenizer.nextToken());

        amountOfFineDust = new int[R][C];
        for (int i = 0; i < R; i++) {
            stringTokenizer = new StringTokenizer(br.readLine());
            for (int j = 0; j < C; j++) {
                amountOfFineDust[i][j] = Integer.parseInt(stringTokenizer.nextToken());
                if(amountOfFineDust[i][j] == -1 && airCleaner == -1) airCleaner = i;
            }
        }

        while (T-- > 0) {
            checkDust();
            spreadDust();
            operateAirCleaner();
        }

        int ans = 0;
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                ans += amountOfFineDust[i][j];
            }
        }
        System.out.println(ans);

    }

    private static void operateAirCleaner() {
        int top = airCleaner;
        int bottom = airCleaner + 1;

        for (int i = top - 1; i > 0; i--) {
            amountOfFineDust[i][0] = amountOfFineDust[i - 1][0];
        }
        for (int i = 0; i < R-1; i++) {
            amountOfFineDust[0][i] = amountOfFineDust[0][i + 1];
        }
        for (int i = 0; i < top - 1; i++) {
            amountOfFineDust[i][C - 1] = amountOfFineDust[i + 1][C - 1];
        }
        for (int i = C - 1; i > 0; i--) {
            amountOfFineDust[top][i] = amountOfFineDust[top][i - 1];
        }
        amountOfFineDust[top][1] = 0;

        for (int i = bottom + 1; i < R - 1; i++) {
            amountOfFineDust[i][0] = amountOfFineDust[i + 1][0];
        }
        for (int i = 0; i < C - 1; i++) {
            amountOfFineDust[R - 1][i] = amountOfFineDust[R - 1][i + 1];
        }
        for (int i = R - 1; i > bottom ; i--) {
            amountOfFineDust[i][C - 1] = amountOfFineDust[i - 1][C - 1];
        }
        for (int i = C - 1; i > 0; i--) {
            amountOfFineDust[bottom][i] = amountOfFineDust[bottom][i - 1];
        }
        amountOfFineDust[bottom][1] = 0;
    }

    private static void spreadDust() {
        while (!dusts.isEmpty()) {
            fineDust now = dusts.poll();

            if(now.amount < 5) continue;

            int amountOfSpread = now.amount / 5;
            int cnt = 0;

            for (int d = 0; d < 4; d++) {
                int nx = now.x + dx[d];
                int ny = now.y + dy[d];

                if(nx < 0 || ny < 0 || R <= nx || C <= ny) continue;
                if(amountOfFineDust[nx][ny] == -1)  continue;

                amountOfFineDust[nx][ny] += amountOfSpread;
                cnt++;
            }

            amountOfFineDust[now.x][now.y] -= (amountOfSpread * cnt);
        }
    }

    private static void checkDust() {
        dusts = new LinkedList<>();

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (amountOfFineDust[i][j] == -1 || amountOfFineDust[i][j] == 0) continue;

                dusts.add(new fineDust(i, j, amountOfFineDust[i][j]));
            }
        }
    }
}