백준 17144번 - 미세먼지 안녕!

https://www.acmicpc.net/problem/17144

풀이

매 초마다 순서대로 동작을 진행한다.

1. 미세먼지 확산
2. 공기청정기 작동

1. 미세먼지 확산

r x c 배열에 퍼져있는 미세먼지들은 동시에 확산된다.

동시에 확산되기 때문에, (r,c) 위치에 있는 미세먼지는 인접한 네 방향으로 미세먼지를 확산시킴으로서 자신의 남은 미세먼지양은 줄게되고, 동시에 인접한 네 방향으로부터 확산된 미세먼지의 양이 추가된다.

-1	10	20
-1	5	6

위와 같은 모양으로 미세먼지가 존재한다고 했을 때 (-1은 공기청정기), (0,1) 위치의 미세먼지가 인접한 네 방향으로 2만큼의 미세먼지를 확산시키고, 자산의 미세먼지 양은 -4만큼 감소한다.

-1	10 - 4	20 + 2
-1	5 + 2	6

그리고 동시에, (0,2) 위치에 있는 미세먼지 또한 인접한 네 방향으로 미세먼지를 4만큼 확산시키고(처음 갖고있던 미세먼지 양 / 5), 자신은 -8만큼 감소한다.

-1	10 - 4 + 4	20 + 2 - 8
-1	5 + 2	6 + 4

이런 식으로 동작하기 때문에,

(r,c) 위치에 있는 남는 미세먼지 양 = 인접한 네 방향으로부터 확산되어 온 미세먼지들의 합 + (처음 있던 미세먼지의 양 - 인접한 네 방향으로 확산시킨 미세먼지 양)

으로 나타낼 수 있다.

1) 자신의 위치에 있는 미세먼지들을 일단 인접한 네 방향으로 확산(인접한 위치에 +해줌)

2) 남은 미세먼지 값을 자신의 위치에 +

위 동작을 모든 미세먼지들에 대해 수행하면 남는 미세먼지들이 된다.

그래서 1번을 수행하기 전에 미세먼지가 있는 위치와 양을 큐에 넣고, 위 동작을 큐에서 하나씩 빼면서 수행해준다.

2. 공기청정기 작동

공기청정기로 인해 한 칸씩 이동하는 미세먼지를 구현하면 된다.

바람이 부는 방향으로 한 칸씩 값을 옮기고, 바람이 나오는 부분은 0로 만든다.

모든 미세먼지들을 큐에 넣기

다음 초의 동작을 수행하기 전에, 이차원 배열에 저장되어 있는 미세먼지 값들을 큐에 넣고, 배열의 값은 0으로 초기화한다. (공기청정기 부분 제외)

그래야 다음 초의 작업을 수행할 수 있다.

만약 마지막 초였다면, 큐에 넣지 않고 미세먼지 총 합을 구하면 된다.

소스코드

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class bj17144 {
    // 미세먼지 클래스, 위치와 먼지양을 가짐.
    public static class Dust{
        int y;
        int x;
        int n;

        public Dust(int y, int x, int n) {
            this.y = y;
            this.x = x;
            this.n = n;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        int[] dy={-1,0,1,0};
        int[] dx={0,1,0,-1};
        String str = br.readLine();
        StringTokenizer st=new StringTokenizer(str);
        int r = Integer.parseInt(st.nextToken());   // 행
        int c = Integer.parseInt(st.nextToken());   // 열
        int time = Integer.parseInt(st.nextToken());   // 시간
        int[][] arr = new int[r][c];    // 미세먼지 배열
        int[] air = new int[2];     // 공기청정기 위치
        int airIdx = 0; // 처음 위치 값 받기 위한 임시 인덱스 변수
        Queue<Dust> q = new LinkedList<>(); // 미세먼지 큐, 각 시간마다 존재하는 미세먼지들을 모두 넣어놓는다.
        int sum = 0;    // 정답 미세먼지 양

        // 배열 초기화
        for(int i=0;i<r;i++){
            str = br.readLine();
            st = new StringTokenizer(str);
            for(int j=0;j<c;j++){
                int tmp = Integer.parseInt(st.nextToken());
                // 미세먼지면 큐에 넣고, 공기청정기면 공기청정기 변수 저장
                if(tmp > 0){
                    q.add(new Dust(i,j,tmp));
                }else if(tmp == -1){
                    arr[i][j] = -1;
                    air[airIdx] = i;
                    airIdx+=1;
                }
            }
        }
        // time초 동안 일이 발생
        for(int t = 1; t <= time; t++){
            // 1. 미세먼지 확산
            while(!q.isEmpty()){
                Dust dust = q.remove();
                int remain = dust.n;    // 남는 먼지 양
                int toss = dust.n / 5;  // 주변에 확산할 먼지 양
                // 주변 4방향 확인하여 확산 가능하면 먼지 확산
                for(int d=0;d<4;d++){
                    int ty=dust.y+dy[d];
                    int tx=dust.x+dx[d];
                    // 확산 불가능 조건 체크
                    if(ty<0 || ty>=r || tx<0 || tx>=c){
                        continue;
                    }
                    if(arr[ty][tx] == -1){
                        continue;
                    }
                    // 확산
                    arr[ty][tx]+=toss;  // 기존 위치에 있는 먼지 값에 +해준다.
                    remain-=toss;
                }
                arr[dust.y][dust.x] += remain;   // 남는 먼지양 +해준다.
            }

            // 2. 공기청정기 작동
            // 위쪽 공기청정기
            for(int k=air[0]-1;k>0;k--){
                arr[k][0] = arr[k-1][0];
            }
            for(int k=0;k<c-1;k++){
                arr[0][k] = arr[0][k+1];
            }
            for(int k=0;k<air[0];k++){
                arr[k][c-1] = arr[k+1][c-1];
            }
            for(int k=c-1;k>0;k--){
                arr[air[0]][k] = arr[air[0]][k-1];
                if(k==1){
                    arr[air[0]][k]=0;
                }
            }
            // 아래쪽 공기청정기
            for(int k=air[1]+1;k<r-1;k++){
                arr[k][0] = arr[k+1][0];
            }
            for(int k=0;k<c-1;k++){
                arr[r-1][k] = arr[r-1][k+1];
            }
            for(int k=r-1;k>air[1];k--){
                arr[k][c-1] = arr[k-1][c-1];
            }
            for(int k=c-1;k>0;k--){
                arr[air[1]][k] = arr[air[1]][k-1];
                if(k==1){
                    arr[air[1]][k]=0;
                }
            }

            // 3. 미세먼지들 다시 큐에 넣고, 배열 값은 0으로 만들기 (다음 시간 동작들을 위해)
            for(int i=0;i<r;i++){
                for(int j=0;j<c;j++){
                    if(arr[i][j]>0){
                        // 마지막 타임이면 정답 구하고, 아니면 큐에 넣는다.
                        if(t==time) {
                            sum += arr[i][j];
                        }else{
                            q.add(new Dust(i,j,arr[i][j]));
                            arr[i][j] = 0;
                        }
                    }
                }
            }
        }
        bw.write(""+sum);

        bw.flush();
        bw.close();
        br.close();
    }
}