17144번 - 미세먼지 안녕!

1. 문제 정의

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

공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (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초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.

2. 문제 접근

단순히 먼지의 확산이 좌,우,위,아래 밖에 되지 않기 때문에 칸마다 미세먼지를 확산 시킨 후, 공기청정기를 작동시키면 된다.

 

3. 문제 풀이

구현에 있어 몇가지 주의할 점이 있었다. 일단, 먼지는 확산이 우선적으로 일어난 후, 합산된다는 것이다. 따라서 같은 배열 객체에서 먼지 퍼트림과 퍼트러진 먼지를 바로 더해버리면 이상해져 버린다?(문제를 풀어보면 알것이다...) 그래서 A 배열과 spread_dust라는 배열을 따로 두고 문제를 풀었다. A 배열에는 먼지가 퍼트리는 놈의 결과만 놓았고, spread_dust에는 먼지가 퍼져서 나온 결과물들만 집어넣었다. 그래서 한번 먼지의 확산이 있고 난 후, 두 배열을 더해 주었다. 그리고 공기청정기를 작동시켜주면 된다. 공기청정기를 작동시킬 때는 또 A_copoy라는 배열을 만들어서 밀린 먼지의 위치를 여기서 가져다 표현해주었다. 

 

4. 코드

import java.io.*;
import java.util.*;

public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    static int R, C, T, sum;

    static int[][] A, spread_dust, A_copy;

    static ArrayList<Point> air_condition;

    // 아, 오, 위, 왼
    static int[][] dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    static int[] ccw = {1,2,3,0};
    static int[] cw = {1,0,3,2};

    static class Point{
        int x;
        int y;

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

    static void input() {
        R = scan.nextInt();
        C = scan.nextInt();
        T = scan.nextInt();

        A = new int[R][C];

        air_condition = new ArrayList<>();

        for (int i = 0; i < R; i++) {
            String[] lines = scan.nextLine().split(" ");
            for (int j = 0; j < lines.length; j++) {
                if(Integer.parseInt(lines[j]) == -1){
                    air_condition.add(new Point(i,j));
                }
                A[i][j] = Integer.parseInt(lines[j]);
            }
        }
    }

    static void reset_val(){
        spread_dust = new int[R][C];
        A_copy = new int[R][C];
    }

    static void pro() {

        // T초 후 확인
        for (int t = 0; t < T; t++) {

            reset_val();

            // 미세먼지 확산
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    if (A[i][j] == 0 || A[i][j] == -1) continue;
                    dust_spread(i, j);
                }
            }
            // 한번에 퍼진 먼지 합산
            for(int i = 0; i < R; i++){
                for (int j = 0; j < C; j++) {
                    A[i][j] += spread_dust[i][j];
                    A_copy[i][j] = A[i][j];
                }
            }

            // 공기청정기 작동
            circulate(air_condition.get(0).x,air_condition.get(0).y,ccw);
            circulate(air_condition.get(1).x,air_condition.get(1).y,cw);

        }

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (A[i][j] > 0) {
                    sum += A[i][j];
                }
            }
        }

        System.out.println(sum);


    }

    static void circulate(int air_x, int air_y, int[] direction) {
        int x = air_x;
        int y = air_y+1;

        A[x][y] = 0;

        for(int d = 0; d < 4; d++){
            while(true){
                int nx = x + dir[direction[d]][0];
                int ny = y + dir[direction[d]][1];

                if (nx < 0 || ny < 0 || nx >= R || ny >= C) break;
                if (air_x == nx && air_y == ny) break;
                A[nx][ny] = A_copy[x][y];
                x = nx;
                y = ny;
            }
        }


    }

    static void dust_spread(int x, int y) {

        int spread_cnt = 0;

        for (int i = 0; i < 4; i++) {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];


            // 배열 범위가 벗어난 경우
            if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
            // 공기청정기가 있는 경우
            if (A[nx][ny] == -1) continue;
            if(A[x][y] / 5 == 0) continue;
            // 퍼졌다면 +1
            spread_cnt++;
            spread_dust[nx][ny] += A[x][y] / 5;
        }

        // 퍼트린 먼저 크기 보정
        A[x][y] = A[x][y] - A[x][y] / 5 * spread_cnt;

    }

    public static void main(String[] args) {
        input();
        pro();
    }


    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

 

5. 회고

미세먼지 안녕~~