[백준] 17144번 - 미세먼지 안녕! (Gold 4)

문제 링크

백준 17144번 - 미세먼지 안녕! (Gold 4)

문제 설명

방에 설치된 공기청정기의 위치와 각 지점마다 미세먼지의 양이 주어져 있다.
1초마다 아래의 일들이 순서대로 일어난다.

1. 미세먼지가 확산된다.
   • 미세먼지가 있는 모든 칸에서 동시에 확산이 일어난다.
   • 상하좌우 네 방향으로 미세먼지가 있는 양 / 5(소수점은 버린다) 만큼이 확산된다.
   • 인접한 칸에 공기청정기가 있거나 아예 칸이 없으면 그 방향으로는 확산되지 않는다.
2. 공기청정기가 작동한다.
   • 위쪽 공기청정기의 바람은 반시계방향으로, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
   • 바람이 불면 미세먼지는 바람의 방향대로 한칸씩 밀려난다.
   • 공기청정기에서 나온 바람은 미세먼지가 없다.
   • 공기청정기로 들어온 미세먼지는 정화되어 사라진다.

주어진 시간 T초가 지났을 때 방에 남아있는 미세먼지의 전체 양을 구하시오.

정답 코드 및 설명

문제에 주어진 조건을 빠짐없이 구현만 하면 된다.
아래 코드에서 각 파트를 구현한 위치는 다음과 같다.

• 공기청정기의 작동 : 90 ~ 93행
• 확산을 구현한 diffusion 메소드 : 30 ~ 47행
• 위쪽 공기청정기의 바람을 구현한 cleaningUp 메소드 : 50 ~ 64행
• 아래쪽 공기청정기의 바람을 구현한 cleaningDown 메소드 : 67 ~ 81행

가장 신경써서 구현할 부분은 공기청정기의 바람이라고 생각한다.
아래 코드에서는 공기청정기의 바람이 오른쪽으로 부는 부분, 위로 부는 부분, 왼쪽으로 부는 부분, 아래로 부는 부분을 각각 나누어서 구현하였다.

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

public class BOJ17144 {
    static final int[][] NEXT = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int r, c, t;
    int[][] dust;
    ArrayList<Integer> cleanerPositions;

    void input() 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());
        dust = new int[r][c];
        cleanerPositions = new ArrayList<>();
        for (int i = 0; i < r; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < c; j++) {
                dust[i][j] = Integer.parseInt(st.nextToken());
                if (dust[i][j] == -1) cleanerPositions.add(i);
            }
        }
    }

    void diffusion() {
        int[][] next = new int[r][c];
        int nextI, nextJ;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                next[i][j] += dust[i][j];
                if (dust[i][j] == -1) continue;
                for (int[] ints : NEXT) {
                    nextI = i + ints[0];
                    nextJ = j + ints[1];
                    if (!isValid(nextI, nextJ)) continue;
                    if (dust[nextI][nextJ] == -1) continue;
                    next[nextI][nextJ] += dust[i][j] / 5;
                    next[i][j] -= dust[i][j] / 5;
                }
            }
        }
        dust = next;
    }

    void cleaningUp() {
        int cleaner = cleanerPositions.get(0);
        for (int i = cleaner - 1; i > 0; i--) {
            dust[i][0] = dust[i - 1][0];
        }
        for (int j = 0; j < c - 1; j++) {
            dust[0][j] = dust[0][j + 1];
        }
        for (int i = 0; i < cleaner; i++) {
            dust[i][c - 1] = dust[i + 1][c - 1];
        }
        for (int j = c - 1; j > 1; j--) {
            dust[cleaner][j] = dust[cleaner][j - 1];
        }
        dust[cleaner][1] = 0;
    }

    void cleaningDown() {
        int cleaner = cleanerPositions.get(1);
        for (int i = cleaner + 1; i < r - 1; i++) {
            dust[i][0] = dust[i + 1][0];
        }
        for (int j = 0; j < c - 1; j++) {
            dust[r - 1][j] = dust[r - 1][j + 1];
        }
        for (int i = r - 1; i > cleaner; i--) {
            dust[i][c - 1] = dust[i - 1][c - 1];
        }
        for (int j = c - 1; j > 1; j--) {
            dust[cleaner][j] = dust[cleaner][j - 1];
        }
        dust[cleaner][1] = 0;
    }

    boolean isValid(int i, int j) {
        return i >= 0 && i < r && j >= 0 && j < c;
    }

    void solution() throws IOException {
        input();
        while (t-- > 0) {
            diffusion();
            cleaningUp();
            cleaningDown();
        }
        int currDust = 2;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                currDust += dust[i][j];
            }
        }
        System.out.println(currDust);
    }

    public static void main(String[] args) throws IOException {
        new BOJ17144().solution();
    }
}