[BOJ] 17144.미세먼지 안녕!(시뮬레이션).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

시뮬레이션은 하라는대로 구현을 잘 하는 것이 중요하므로

조건을 잘 확인해보자.

* 공기청정기는 항상 1번 열에 설치

* 크기는 두 행을 차지

1. 미세먼지 확산

(r, c)에 있는 미세먼지는 인접한 네 방향으로 확산

인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다

확산되는 양은 Ar,c/5이고 소수점은 버린다.

(r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.

2. 공기청정기 작동

공기청정기에서는 바람이 나온다.

위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환

바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.

공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화

//

그렇다면, 

어떻게 구현을 할지 동작을 생각해보자.

1. 집 정보를 입력받으면서 공기청정기 위치를 저장

2. 미세먼지가 있는 공간을 확인

   -> 미세먼지가 있는 좌표와 미세먼지 양을 큐에 담았다.

   -> 이 부분은 배열을 복사할 경우 필요 없는 과정이다.

3. 미세먼지 확산

  - >미세먼지 양이 5보다 작은 경우는 어차피 0이 확산되므로 pass 해주자.

  -> 여기서 착각할 수 있는게, 확산은 동시에 이루어지므로 확산되기 전 미세먼지 양의 / 5 만큼을 확산시켜야 한다.

4. 공기청정기 작동

  -> 순환방향으로 값을 이동시키면, 방향이 바뀌는 부분에서 살짝 복잡하다. 

      그래서 방향으로 흘러가는 것이 아니라, 방향의 흐름을 역류한다는 느낌으로 값을 당겨주면 더 쉽게 이동시킬 수 있다.

#. Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class BOJ17144 {
 
    static int R, C, T, map[][];
    static int cleaner = -1;
    static Queue<Dust> dusts;
    static int[] dx = {0, -1, 0, 1}, dy = {1, 0, -1, 0};
    static class Dust {
        int x, y, w;
 
        public Dust(int x, int y, int w) {
            super();
            this.x = x;
            this.y = y;
            this.w = w;
        }
        
    }
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        R = Integer.parseInt(st.nextToken()); // 행
        C = Integer.parseInt(st.nextToken()); // 열
        T = Integer.parseInt(st.nextToken()); // 초
        map = new int[R][C];
        
        // map 정보 저장
        for (int i = 0; i < R; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < C; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                
                // 공기청정기 위치 저장    
                if(cleaner == -1 && map[i][j] == -1) {
                    cleaner = i;
                }
            }
        }
        
        for (int time = 0; time < T; time++) {
            
            // 미세먼지가 있는 공간 확인
            checkDust();
            
            // 미세먼지 확산
            spread();
            
            // 공기청정기 작동
            operate();
 
        }
        
        int res = 0;
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if(map[i][j] == -1) continue;
                res += map[i][j];
            }
        }
        
        System.out.println(res);
    }
 
    private static void checkDust() {
        
        dusts = new LinkedList<>();
        
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if(map[i][j] == -1 || map[i][j] == 0) continue;
                // 미세먼지가 있는 공간과 미세먼지 양
                dusts.add(new Dust(i, j, map[i][j]));
            }
        }
        
    }
 
    private static void spread() {
        
        while(!dusts.isEmpty()) {
            
            Dust now = dusts.poll();
            // 확산될 먼지가 없으면
            if(now.w < 5) continue;
            // 확산되는 양은 Ar,c/5
            int amountOfSpread = now.w / 5;
            int cnt = 0;
            // 인접한 방향으로 확산
            for (int d = 0; d < 4; d++) {
                int xx = now.x + dx[d];
                int yy = now.y + dy[d];
                // 범위를 벗어나면
                if(xx < 0 || xx >= R || yy < 0 || yy >= C) continue;
                // 공기청정기가 있으면
                if(map[xx][yy] == -1) continue;
                
                map[xx][yy] += amountOfSpread;
                ++cnt;
            }
            
            // 남은 미세먼지 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수)
            map[now.x][now.y] -= amountOfSpread * cnt;
        }
        
    }
 
    // 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동
    private static void operate() {
        
        int top = cleaner;
        int down = cleaner + 1;
        
        // 위쪽 공기청정기의 바람은 반시계방향 순환,
        // 아래로 당기기
        for (int i = top - 1; i > 0; i--) 
            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 < top; i++) 
            map[i][C - 1] = map[i + 1][C - 1];
        // 오른쪽으로 당기기
        for (int i = C - 1; i > 1; i--) 
            map[top][i] = map[top][i-1];
        // 공기청정기에서 부는 바람은 미세먼지가 없는 바람
        map[top][1] = 0;
        
        // 아래쪽 공기청정기의 바람은 시계방향으로 순환
        // 위로 당기기
        for (int i = down + 1; i < R - 1; i++) 
            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 > down; i--) 
            map[i][C - 1] = map[i - 1][C - 1];
        // 오른쪽으로 당기기
        for (int i = C - 1; i > 1; i--) 
            map[down][i] = map[down][i - 1];
        // 공기청정기에서 부는 바람은 미세먼지가 없는 바람
        map[down][1] = 0;
    }
    
}