[BaekJoon] 백준 - 미세먼지 안녕!

 

 

공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.

1초 동안 아래 적힌 일이 순서대로 일어난다.

1. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
   • (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
   • 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
   • 확산되는 양은 Ar,c/5이고 소수점은 버린다.
   • (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.
2. 공기청정기가 작동한다.
   • 공기청정기에서는 바람이 나온다.
   • 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
   • 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
   • 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.

 

 

 

격자 위에 놓인 미세먼지를 확산시키고 공기청정기를 가동한 후에 격자 위에 남아있는 미세먼지를 구하는 문제.

 

문제에 나타난 단계를 잘 따라가면 된다. 

 

 

미세먼지 확산 Diffuse 함수

미세먼지는 동시에 확산되기 때문에 2차원 배열을 한개 더 생성하여 미세먼지의 확산만 고려하였고

원래 있던 배열에는 미세먼지가 확산되고 난 이후의 값을 저장했다. 

 

미세먼지 확산이 완료되면 두 배열의 값을 합쳐서 최종 상태가 된다. 

 

 

공기청정기 Cleaner 함수

공기청정기는 각 시계방향과 반시계 방향으로 총 2회 가동이 되며 바람은 격자의 끝에 다다랐을 때 변경된다. 

 

direction 배열 (d1, d2, d3, d4) 를 사용하여 시계방향(d1, d2)과 반시계방향(d3, d4)을 나누었고 

청소 단계는 처음 A 를 똑같이 복사한 배열을 생성해서 A의 값을 변경해주는 방식으로 했다. 

 

첫 시작점의 미세먼지는 항상 0이 되고, 방향에 따라 한칸씩 옮겨준다. 

다음 위치가 공기청정기가 있는 위치라면, 옮기지 않고 그대로 종료한다. 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int[][] A;
    static int R;
    static int C;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] tmp = br.readLine().split(" ");
        
        R = Integer.parseInt(tmp[0]);
        C = Integer.parseInt(tmp[1]);
        int T = Integer.parseInt(tmp[2]);
        A = new int[R][C];
        
        int cleaner = 0;
        int cleaner2 = 0;
        
        boolean flag = false;
        
        for(int i = 0; i<R; i++) {
            String[] input = br.readLine().split(" ");
            for(int j = 0; j<C; j++) {
                A[i][j] = Integer.parseInt(input[j]);
                
                if (A[i][j] == -1) {
                    if (!flag) {
                        cleaner = i; cleaner2 = i + 1;
                        flag = true;
                    }
                }
            }
        }
        int[] d1 = {0, -1, 0, 1};
        int[] d2 = {1, 0, -1, 0};
        
        int[] d3 = {0, 1, 0, -1};
        int[] d4 = {1, 0, -1, 0};
        
        int count = 0;
        while (count < T) {
            diffuse();
            clean(cleaner, d1, d2);
            clean(cleaner2, d3, d4);
            count ++;
            
        }
        
        int answer = 0;
        for(int i = 0; i<R; i++) {
            for(int j = 0; j<C; j++) {
                if (A[i][j] != -1)
                    answer += A[i][j];
            }
        }
        
        System.out.println(answer);
    }
    
    public static void diffuse() {
        int[][] new_A = new int[R][C];
        int[] d1 = { -1, 1, 0, 0};
        int[] d2 = { 0, 0, -1, 1};
        
        for(int i = 0; i<R; i++) {
            for(int j = 0; j<C; j++) {
                new_A[i][j] = 0;
            }
        }
        
        
        for(int i = 0; i<R; i++) {
            for(int j = 0; j<C; j++) {
                if ( A[i][j] > 0 ) {
                    int dust = A[i][j];
                    int count = 0;
                    
                    for(int k = 0; k<4; k++) {
                        if (i + d1[k] >= 0 && j + d2[k] >= 0 && i + d1[k] < R && j + d2[k] < C) {
                            if (A[i + d1[k]][j + d2[k]] != -1) {
                                new_A[i + d1[k]][j + d2[k]] += dust / 5;
                                count ++;
                            }
                        }
                    }
                    
                    A[i][j] = dust - ( (dust/5) * count );
                }
            }
        }
        
        for(int i = 0; i<R; i++) {
            for(int j = 0; j<C; j++) {
                A[i][j] += new_A[i][j];
            }
        }
    }
    
    public static void clean(int c_i, int[] d1, int[] d2) {
        int[][] tmp = deepCopy(A);
        int start_i = c_i;
        int start_j = 1;
        A[start_i][start_j] = 0;
        
        for(int i = 0; i<4; i++) {
            while(true) {
                int new_i = start_i + d1[i];
                int new_j = start_j + d2[i];
                
                if (!(new_i >= 0 && new_i < R && new_j >= 0 && new_j < C))
                    break;
                
                if (new_i == c_i && new_j == 0)
                    break;
                
                A[new_i][new_j] = tmp[start_i][start_j];
                start_i = new_i;
                start_j = new_j;
            }
        }
    }
    
    public static int[][] deepCopy(int[][] target) {
        int[][] result = new int[R][C];
        
        for(int i = 0; i<R; i++) {
            for(int j = 0; j<C; j++) {
                result[i][j] = target[i][j];
            }
        }
        
        return result;
    }
}