미세먼지 안녕

📍 문제 설명

 

💡 접근

시뮬레이션 문제에 아직 익숙하지 않아서 문제 이해도 어렵고 코드도 지저분하다.

계속해서 생각하면서 푸는 연습을 하자!

 

1.공기청정기는 1열에 설치되지만 행은 지정된 것이 아니므로 위치를 찾을 수 있는 변수 설정

2.t초간 미세먼지가 있는 공간에 대해서 미세먼지를 확산& 공기청정기 작동

3.확산은 동시에 진행되어 남은 미세먼지 양과 확산되는 양이 모두 더해져야 한다.

다른 블로그와 코드를 비교해보니 원본 배열 하나만 이용하더라도 풀이가 가능하다.

4.모든 미세먼지가 확산되었으면 공기청정기가 작동되어 순환방향에 따라 값이 변경된다.

 

 

👩‍💻 코드

import java.util.*;

public class Main {
    static int n, m, k, answer, cnt, max, min, sum, count, r, c, t, top, down;
    static int[][] board, clone, dis;
    static boolean[][] visited;
    static int[] ch, pm, combi, graph, temp;
    static boolean flag = false;
    static int[] dx = {-1,0,1,0,}; //북동남서
    static int[] dy = {0,1,0,-1};
    static ArrayList<Integer> list = new ArrayList<>();
    static Queue<Point> q;
    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);

        r = kb.nextInt();
        c = kb.nextInt();
        t = kb.nextInt();
        board = new int[r+1][c+1];
        //확산되는 미세먼지 기록
        dis = new int[r+1][c+1];
        for(int i = 1; i <= r; i++) {
            for(int j = 1; j <= c; j++) {
                board[i][j] = kb.nextInt();
                if(board[i][j] == -1) {
                    dis[i][j] = -1;
                    //공기청정기 아래위치
                    down = i;
                }
            }
        }

        //★확산은 동시에 일어난다.
        //모든 지점에 대해서 탐색해서 미세먼지 확산시키기

        q = new LinkedList<>();
        //t초간 미세먼지 확산 및 공기청정기 작동
        for(int i = 1; i <= t; i++) {
            for (int j = 1; j <= r; j++) {
                for (int k = 1; k <= c; k++) {
                    if (board[j][k] > 0) {
                        //확산해야하는 지점 큐에 넣기
                        q.offer(new Point(j, k, i));
                        T.solution(j, k, i);
                    }
                }
            }
            //공기청정기 동작시키기
            T.airCleaner();

            //확산된 미세먼지 + 공기청정기 동작 후의 미세먼지를 원본 배열에 넣기
            board = clone;
            //확산용 배열
            dis = new int[r+1][c+1];
        }
        for(int a = 1; a <= r; a++) {
            for(int b = 1; b <= c; b++) {
                if(board[a][b] > 0) sum += board[a][b];
            }
        }
        System.out.println(sum);


    }

    private void airCleaner() {
        //공기청정기 동작용 배열
        clone = new int[r+1][c+1];

        top = down - 1;

        //3행,4행의 값들을 1열부터 8열(c)까지 오른쪽으로 옮긴다. 
        //그리고 3행 8열(c) 부터 1행 8열 까지 값들을 위로 옮긴다. 
        //4행 8열(c) 부터 7행 8열(c) 까지 값들을 아래로 옮긴다. 
        //1행,7행 의 값들을 8열(c)부터 1열 까지의 값들은 왼쪽으로 옮긴다. 
        //그리고 1행 1열의 값은 아래로 (2행까지) 
        //1행 7열의 값은 위로 옮긴다. 

        //공기청정기의 행들은 오른쪽으로
        for(int i = top; i <= down; i++) {
            for(int j = c; j >= 3; j--) {
                clone[i][j] = dis[i][j-1];
            }
        }
        //오른쪽에서 위로
        for(int i = 1; i < top; i++) {
            clone[i][c] = dis[i+1][c];
        }
        //오른쪽에서 아래로
        for(int i = r; i > down; i--) {
            clone[i][c] = dis[i-1][c];
        }

        //왼쪽으로
        for(int i = 1; i < c; i++) {
            clone[1][i] = dis[1][i+1];
            clone[r][i] = dis[r][i+1];
        }

        //왼쪽에서 아래로
        //2행 1열에 1행 1열
        for(int i = top-1; i > 1; i--) {
            clone[i][1] = dis[i-1][1];
        }

        //왼쪽에서 위로
        //6행 1열에 7행 1열
        //5행 1열에 6행 1열
        for(int i = r-1; i > down; i--) {
            clone[i][1] = dis[i+1][1];
        }


        //공기 청정기 영향 안받는 곳은 그냥 넣어주기
        for(int i = 2; i < top; i++) {
            for (int j = 2; j < c; j++) {
                clone[i][j] = dis[i][j];
            }
        }
        for(int i = down+1; i < r; i++) {
            for(int j = 2; j < c; j++) {
                clone[i][j] = dis[i][j];
            }
        }
        //공기청정기 -1로
        clone[top][1] = -1;
        clone[down][1] = -1;

    }

    private void solution(int x, int y, int second) {
        //확산된 방향의 갯수 확인
        cnt = 0;

        while(!q.isEmpty()) {
            Point cp = q.poll();
            //4방향으로 확산시키기
            for (int i = 0; i < 4; i++) {
                int nx = cp.x + dx[i];
                int ny = cp.y + dy[i];
                if (nx <= 0 || ny <= 0 || nx > r || ny > c || board[nx][ny] == -1) continue;
                //확산되는 양
                dis[nx][ny] += board[x][y] / 5;
                cnt++;
            }
            //현 지점은 남은 미세먼지 양을 넣기
            dis[x][y] += board[x][y] - (board[x][y] / 5) * cnt;
        }
    }

    private static class Point {
        private int x;
        private int y;
        private int second;

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