BOJ17144_미세먼지 안녕!

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

문제요약

1. 공기청정기는 항상 왼쪽 열에 설치 , 크기는 두 행을 차지(공기청정기가 두개)

1초동안 일어나는 일

1. 미세먼지가 확산 , 확산은 모든 칸에서 동시에 발생함

(1) 미세먼지는 인접한 네 방향으로 확산

(2) 인접한 방향에 공기청정기가 있거나 , 칸이 없으면 확산 못함

(3) 확산되는 양은 Ar,c / 5 소수점은 버림

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

2. 공기청정기 작동

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

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

(3) 공기청정기로 들어간 미세먼지는 모두 정화

(4) 공기청정기에서 나온 바람은 미세먼지 = 0

출력

T초가 지난 후 map에 남은 미세먼지를 총 합한 양

문제issue

1. 미세먼지는 동시에 확산됨!!

2. 공기청정기에 의해 움직이는 미세먼지를 q 구현 말고 더 빠른 방법 생각해봐야함

해결흐름

1. map에 입력 시 공기청정기의 위치를 저장 해둔다.

2. 미세먼지가 먼저 확산된다.

(1) map을 돌면서 미세먼지 크기가 5 이상인 곳의 위치와 그때의 크기를 저장해둔다. (5로 나눴을 때 몫을 사용하기 때문 , 미세먼지는 동시에 확산되기 때문)

(2) 처음 미세먼지 위치에서 사방을 봐서 범위 안이고 공기청정기가 아니면 확산 시킨다.

(3) 처음 미세먼지 위치의 값을 갱신한다.

3. 공기청정기를 가동 시킨다.

(1) 큐를 이용하여 구현하였다.

(2) 시간이 아슬아슬하여 다른 방법도 생각해보면 좋을듯 하다.

4. map안의 값이 0보다 큰 곳의 값만 합하여 출력한다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    static class pair{
        int r;
        int c;
        int dust;
        public pair(int r, int c, int dust) {
            super();
            this.r = r;
            this.c = c;
            this.dust = dust;
        }
    }
    
    static class air_cleaner{
        int r;
        int c;
        public air_cleaner(int r, int c) {
            super();
            this.r = r;
            this.c = c;
        }
    }
    
    private static int[] dr = {-1,0,1,0};
    private static int[] dc = {0,1,0,-1};
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
        int R = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        int T = Integer.parseInt(st.nextToken());
        List<air_cleaner> list = new ArrayList<>();
        
        int[][] map = new int[R][C];
        for (int i = 0; i < R; i++) {
            st = new StringTokenizer(br.readLine().trim(), " ");
            for (int j = 0; j < C; j++) {
                int x = Integer.parseInt(st.nextToken());
                map[i][j] = x;
                if(x == -1) {
                    list.add(new air_cleaner(i, j));
                }
            }
        }
        
        while(T > 0) {
            T--;
            // 미세먼지 확산
            Queue<pair> q1 = new LinkedList<>();
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    if(map[i][j] >= 5) {
                        q1.add(new pair(i, j, map[i][j]));
                    }
                }
            }
            while(!q1.isEmpty()) {
                pair p = q1.poll();
                int f_dust = p.dust;
                int cnt = 0;
                for (int i = 0; i < 4; i++) {
                    int nr = p.r + dr[i];
                    int nc = p.c + dc[i];
                    if(nr >= 0 && nr < R && nc >= 0 && nc < C) {
                        if(map[nr][nc] != -1) {
                            map[nr][nc] += f_dust / 5;
                            cnt++;
                        }
                    }
                }
                map[p.r][p.c] -= (f_dust / 5) * cnt;
            }
            
            // 공기청정기 작동
            for (int i = 0; i < list.size(); i++) {
                int air_r = list.get(i).r;
                int air_c = list.get(i).c;
                Queue<Integer> q = new LinkedList<>();
                if(i == 0) {
                    //1
                    q.add(0);
                    for (int j = air_c+1; j < C; j++) {
                        q.add(map[air_r][j]);
                    }
                    for (int j = air_c+1; j < C; j++) {
                        map[air_r][j] = q.poll();
                    }
                    //2
                    for (int j = air_r-1; j >= 0; j--) {
                        q.add(map[j][C-1]);
                    }
                    for (int j = air_r-1; j >= 0; j--) {
                        map[j][C-1] = q.poll();
                    }
                    //3
                    for (int j = C-2; j >= 0; j--) {
                        q.add(map[0][j]);
                    }
                    for (int j = C-2; j >= 0; j--) {
                        map[0][j] = q.poll();
                    }
                    //4
                    for (int j = 1; j < air_r; j++) {
                        q.add(map[j][0]);
                    }
                    for (int j = 1; j < air_r; j++) {
                        map[j][0] = q.poll();
                    }
                    q.clear();
                }
                else if(i == 1) {
                    // 1
                    q.add(0);
                    for (int j = air_c+1; j < C; j++) {
                        q.add(map[air_r][j]);
                    }
                    for (int j = air_c+1; j < C; j++) {
                        map[air_r][j] = q.poll();
                    }
                    // 2
                    for (int j = air_r+1; j < R; j++) {
                        q.add(map[j][C-1]);
                    }
                    for (int j = air_r+1; j < R; j++) {
                        map[j][C-1] = q.poll();
                    }
                    
                    // 3
                    for (int j = C-2; j >= 0; j--) {
                        q.add(map[R-1][j]);
                    }
                    for (int j = C-2; j >= 0; j--) {
                        map[R-1][j] = q.poll();
                    }
                    
                    // 4
                    for (int j = R-2; j > air_r; j--) {
                        q.add(map[j][0]);
                    }
                    for (int j = R-2; j > air_r; j--) {
                        map[j][0] = q.poll();
                    }
                    q.clear();
                }
            }
        } // end of while
        
        int sum = 0;
        for (int j = 0; j < R; j++) {
            for (int k = 0; k < C; k++) {
                if(map[j][k] > 0) {
                    sum += map[j][k];
                }
            }
        }
        System.out.println(sum);
        
    } // end of main
} // end of class