[Java][자바][17144번] 미세먼지 안녕!

문제

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.

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

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

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

다음은 확산의 예시이다.

왼쪽과 오른쪽에 칸이 없기 때문에, 두 방향으로만 확산이 일어났다.

인접한 네 방향으로 모두 확산이 일어난다.

공기청정기가 있는 칸으로는 확산이 일어나지 않는다.

공기청정기의 바람은 다음과 같은 방향으로 순환한다.

방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.

입력

첫째 줄에 R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000) 가 주어진다.

둘째 줄부터 R개의 줄에 Ar,c (-1 ≤ Ar,c ≤ 1,000)가 주어진다. 공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양이다. -1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.

출력

첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.

 

생각

순차적으로 진행하면 된다. 먼저 확산을 시켜준 후 공기청정기가 작동하여 미세먼지를 이동시키면 된다.

확산을 할 때, 한 map에서 순차적으로 진행하면 다른 칸에서 확산을 해서 영향을 받아 영향을 받은 이후에 확산을 해서 결과가 다르게 나올 수 있다. 그러므로 원래 정보를 담은 map과 확산의 정보를 받는 tmp_map을 만들어서 확산을 시켜준 후 마지막에 더해준다.

 

후에 회전은 배열돌리기 문제처럼 회전해주면 된다. 물론 나는 깔끔하게 못하고 무식하게 했지만 여러분들은 더 잘 할 수 있을거라 믿는다!! 주석에 더 자세한 설명을 적도록 하겠다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
    static int map[][];
    static boolean visited[][];
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static int R,C,T;
    static int cleanerCount = 0;
    static int[] cleanerX = new int[2];
    static int[] cleanerY = new int[2];
    static int totalDust;
 
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
        String[] input = br.readLine().split(" ");
        R = Integer.parseInt(input[0]);
        C = Integer.parseInt(input[1]);
        T = Integer.parseInt(input[2]);
        
        map = new int[R][C];
        visited = new boolean[R][C];
        
        for(int i=0; i<R; i++) {
            String[] str = br.readLine().split(" ");
            for(int j=0; j<C; j++) {
                map[i][j] = Integer.parseInt(str[j]);
                if(map[i][j] == -1) {
                    cleanerX[cleanerCount] = i;
                    cleanerY[cleanerCount] = j;
                    cleanerCount++;
                }
            }
        }
        //0초에서 diffustion을 시작한다.
        diffusion(0);
        System.out.println(totalDust);
        
    }
    
    static void diffusion(int t) {
        int[][] tmp_map = new int[R][C];
        int count = 0;
        //T초가 되면 남아있는 먼지를 구해주고 종료한다.
        if(t == T) {
            totalDust = sumDust();
            return;
        }
        
        for(int i=0; i<R; i++) {
            for(int j=0; j<C; j++) {
                if(map[i][j] != 0 && map[i][j] != -1) {
                    for(int k=0; k<4; k++) {
                        int x1 = i + dx[k];
                        int y1 = j + dy[k];
                        //tmp_map에 확산된 먼지들을 넣는다.
                        if(x1>=0 && x1<R && y1>=0 && y1<C &&
                                map[x1][y1] != -1) {
                            tmp_map[x1][y1] += map[i][j]/5;
                            count++;
                        }
                    }
                    //원래 map에서는 확산이 되었으므로 1/5씩 감소시킨다.
                    map[i][j] -= map[i][j]/5 * count;
                    count = 0;
                }
            }
        }
        //확산이 종료되었으면 map에 tmp_map을 더해주고 공기청정기 동작을 시작한다.
        sum(tmp_map);
        startCleaner();    
        diffusion(t+1);
    }
    
    static void sum(int[][] tmp) {
        for(int i=0; i<R; i++) {
            for(int j=0; j<C; j++) {
                map[i][j] += tmp[i][j];
            }
        }
    }
    //각 방향으로 미세먼지가 이동하도록 짜준다.
    static void startCleaner() {
        for(int i=cleanerX[0]-1; i>=0; i--) {
            if(i!=0) {
                map[i][0] = map[i-1][0];
            }
        }
        
        for(int i=0; i<C-1; i++) {
            map[0][i] = map[0][i+1];
        }
        
        for(int i=0; i<cleanerX[0]; i++) {
            map[i][C-1] = map[i+1][C-1];
        }
        
        for(int i=C-1; i>=1; i--) {
            map[cleanerX[0]][i] = map[cleanerX[0]][i-1];
            
            if(i==1) {
                map[cleanerX[0]][i] = 0;
            }
        }
        
        for(int i=cleanerX[1]+1; i<R; i++) {
            if(i!=R-1) {
                map[i][0] = map[i+1][0];
            }
        }
        
        for(int i=0; i<C-1; i++) {
            map[R-1][i] = map[R-1][i+1];
        }
        
        for(int i=R-1; i>cleanerX[1]; i--) {
            map[i][C-1] = map[i-1][C-1];
        }
        
        for(int i=C-1; i>=1; i--) {
            map[cleanerX[1]][i] = map[cleanerX[1]][i-1];
            
            if(i==1) {
                map[cleanerX[1]][i] = 0;
            }
        }
    }
    
    static int sumDust() {
        int total = 0;
        
        for(int i=0; i<R; i++) {
            for(int j=0; j<C; j++) {
                if(map[i][j] != -1) {
                    total += map[i][j];
                }
            }
        }
        
        return total;
    }
}
 

인턴과 하반기를 동시에 준비하느라 2주간 글을 쓰지 못했다.. 삼성 A형도 시험을 봤지만 후후,,,,박살나버렸다... 다른 유형이 나올 줄은 아무도 생각 못했겠지 ㅠㅠㅠ 코테를 보려면 알고리즘을 풀테니 열심히 정리해봐야겠다!!