백준 17144번 미세먼지 안녕

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 Bye_dust {
    static int R;
    static int C;
    static int T;
    static int[][] map;
    static int[] dr = {0,1,0,-1};
    static int[] dc = {1,0,-1,0};
    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];
        boolean first = true;
        Queue<int[]> que = new LinkedList<>();
        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());

            }
        }
        for (int k = 0; k < T; k++) {
            int[][] copymap = new int[R][C];
            que.clear();
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    if (map[i][j] != 0 && map[i][j] != -1) {
                        que.add(new int[]{i, j});
                    }

                    copymap[i][j] = map[i][j];
                }
            }
            bfs(que,copymap);
            for (int t = 2; t < R - 2; t++) {
                if (map[t][0] != -1)
                    continue;
                if (first) {
                    first = false;
                    int pre = map[t][1];
                    map[t][1] = 0;
                    for (int i = 1; i < C - 1; i++) {
                        int next = map[t][i + 1];
                        map[t][i + 1] = pre;
                        pre = next;
                    }
                    for (int i = t; i > 0; i--) {
                        int next = map[i - 1][C - 1];
                        map[i - 1][C - 1] = pre;
                        pre = next;
                    }
                    for (int i = C - 1; i > 0; i--) {
                        int next = map[0][i - 1];
                        map[0][i - 1] = pre;
                        pre = next;
                    }
                    for (int i = 0; i < t; i++) {
                        int next = map[i + 1][0];
                        map[i + 1][0] = pre;
                        pre = next;
                    }
                    map[t][0] = -1;
                } else {
                    first = true;
                    int pre = map[t][1];
                    map[t][1] = 0;
                    for (int i = 1; i < C - 1; i++) {
                        int next = map[t][i + 1];
                        map[t][i + 1] = pre;
                        pre = next;
                    }
                    for (int i = t; i < R - 1; i++) {
                        int next = map[i + 1][C - 1];
                        map[i + 1][C - 1] = pre;
                        pre = next;
                    }
                    for (int i = C - 1; i > 0; i--) {
                        int next = map[R - 1][i - 1];
                        map[R - 1][i - 1] = pre;
                        pre = next;
                    }
                    for (int i = R - 1; i > t; i--) {
                        int next = map[i - 1][0];
                        map[i - 1][0] = pre;
                        pre = next;
                    }
                    map[t][0]=-1;
                }

            }

        }

        int sum = 0;
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                sum += map[i][j];
            }
        }
        System.out.println(sum+2);
    }
    public static void bfs(Queue<int[]> que,int[][] copymap){

        while(!que.isEmpty()){
            int count = 0;
            int[] current = que.poll();
            int crow = current[0];
            int ccol = current[1];
            int temp = 0;
            for(int i = 0; i<4; i++){
                int nrow = crow + dr[i];
                int ncol = ccol + dc[i];

                if(nrow<0||ncol<0 ||nrow>=R||ncol>=C)
                    continue;
                if(map[nrow][ncol]==-1)
                    continue;
                temp += copymap[crow][ccol]/5;
                map[nrow][ncol] += copymap[crow][ccol]/5;
                count++;
            }
            if(count != 0){
                map[crow][ccol] -= temp ;
            }

        }

    }
}

풀이방법

1. 크게 분류하면 초마다 확산하는 로직, 공기청정기로 순환하는 로직 2가지로 구분해서 푼다.
2. 매 초 맵을 탐색하며 미세먼지가 있는 칸을 확인하고 큐에 담는다.
3. 큐에 있는 값을 동서남북으로 탐색한다. bfs작업을 한번만한다 생각(bfs함수에서 큐에 다시 안담으면 됨).
4. 이때 주의해야 할것이 전부 동시에 확산해야 하는데 bfs로 하면 하나씩 확산하게 된다. 미세먼지가 서로 인접해 있다면 전혀다른 값을 확산하게 된다.
5. 따라서 확산의 주체는 copymap을 통해 사전에 저장해둔 값(인접한 미세먼지가 확산해도 영향이 받지 않도록)을 확산한다.
6. 인접한 동서남북에 확산하는 로직을 작성하고, 확산의 주체는 확산한 값들을 다 더하고 그값을 빼준다. -> 미세먼지 확산 로직 끝
7. 미세먼지 순환시 위쪽 -1은 반시계 방향으로 배열이 이동한다. pre값과 next값을 사용해서 방향마다 포문을 개별로 구현한다.(포문의 범위와 탐색위치설정에 주의하자)
8. 아래쪽 -1도 비슷하게 구현한다.
9. 공기청정기로는 순환되지 않으므로 마지막에 공기청정기 자리에는 -1을 다시 대입해준다. -> 순환로직 끝
10. 맵을 다시 탐색하며 미세먼지를 다 더한다. 공기청정기값이 -1이므로 마지막에 +2해준다.

후기

어려운개념을 쓰는건 아닌거같은데 고려해야할 부분이 많고 여러가지 로직을 붙여놔서 구현하는데 오래걸렸다.