[백준 17144] 미세먼지 안녕! - JAVA

접근 방법

이 문제에서는 spread와 clean이 두 가지 로직이 핵심입니다.

spread

• 1초(각 회차)마다 이중 $for$문 한 번 순회합니다.
• $A_{r,c}/5$ 연산을 해서 확산하는 양 spreadAmount을 구합니다.
• 확산 가능한 곳에 spreadAmout만큼 주고 $A_{r,c}$도 spreadAmount만큼 감소시킵니다.

clean

• 공기 청정기의 위쪽인가 아래쪽인가에 따라 시계방향, 반시계방향으로 나뉩니다.
  • 시계방향: cw = 우 - 하 - 좌 - 상
  • 반시계 방향: ccw = 우 - 상 - 좌 - 하
• 단순 for문으로 각 로직에 맞게 먼지를 이동시킵니다.

문제 후기

이 문제를 보면 조건 자체는 골드 4 치고는 단순하다고 생각했지만
문제를 푸는데 생각보다 시간이 많이 소요됐습니다.
구현 문제를 풀다보면 어떤 알고리즘이 필요한지 명확한 문제를 풀 때보다 더 어려운 것 같습니다.
지식의 저주에 걸려 자꾸만 최적화를 고민하다보니 10분 ~ 20분 시간을 잡아먹게 되고 자꾸 어려운 길로 가게 되어 다른 문제 풀 때보다 20분~30분 정도 많이 소요되는 것 같습니다..

구현 문제는 최적화를 신경쓰지 않고 최대한 빠르게 구현하는 습관을 들여야겠다는 생각을 하게 되었습니다.. 최적화는 그 이후에..

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Main {
    static StringTokenizer st;
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, -1, 0, 1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        int R = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        int T = Integer.parseInt(st.nextToken());
        int[][] room = new int[R][C];

        int y = 0;
        int x = 0;
        for (int i = 0; i < R; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < C; j++) {
                room[i][j] = Integer.parseInt(st.nextToken());

                if (room[i][j] == -1) {
                    y = i;
                    x = j;
                }
            }
        }

        System.out.println(getAnswer(R, C, T, room, y, x));
    }

    static int getAnswer(int R, int C, int T, int[][] current, int clean_y, int clean_x) {
        int[][] next = new int[R][C];
        arrayCopy(current, next, R, C);

        while (T > 0) {
            findSpreadableDust(current, next, R, C);

            clean(next, R, C, clean_y, clean_x);

            arrayCopy(next, current, R, C);

            T--;
        }

        int answer = 0;
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (next[i][j] > 0) answer += next[i][j];
            }
        }

        return answer;
    }

    private static void findSpreadableDust(int[][] current, int[][] next, int r, int c) {
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (current[i][j] >= 5) spread(current, next, i, j, r, c);
            }
        }
    }

    private static void clean(int[][] next, int r, int c, int clean_y, int clean_x) {
        cw(next, r, c, clean_y, clean_x);
        ccw(next, c, clean_y-1, clean_x);
    }

    private static void cw(int[][] room, int r, int c, int sy, int sx) {
        int pushValue = 0;
        int tmp;
        for (int j = sx+1; j < c; j++) {
            tmp = room[sy][j];
            room[sy][j] = pushValue;
            pushValue = tmp;
        }

        for (int i = sy+1; i < r; i++) {
            tmp = room[i][c-1];
            room[i][c-1] = pushValue;
            pushValue = tmp;
        }

        for (int j = c-2; j >= 0; j--) {
            tmp = room[r-1][j];
            room[r-1][j] = pushValue;
            pushValue = tmp;
        }

        for (int i = r-2; i > sy; i--) {
            tmp = room[i][0];
            room[i][0] = pushValue;
            pushValue = tmp;
        }
    }

    private static void ccw(int[][] room, int c, int sy, int sx) {
        int pushValue = 0;
        int tmp;
        for (int j = sx+1; j < c; j++) {
            tmp = room[sy][j];
            room[sy][j] = pushValue;
            pushValue = tmp;
        }

        for (int i = sy-1; i >= 0; i--) {
            tmp = room[i][c-1];
            room[i][c-1] = pushValue;
            pushValue = tmp;
        }

        for (int j = c-2; j >= 0; j--) {
            tmp = room[0][j];
            room[0][j] = pushValue;
            pushValue = tmp;
        }

        for (int i = 1; i < sy; i++) {
            tmp = room[i][0];
            room[i][0] = pushValue;
            pushValue = tmp;
        }
    }

    private static void arrayCopy(int[][] target, int[][] copy, int R, int C) {
        for (int i = 0; i < R; i++) {
            System.arraycopy(target[i], 0, copy[i], 0, C);
        }
    }


    private static void spread(int[][] current, int[][] next, int y, int x, int R, int C) {
        int spreadAmount = current[y][x] / 5;

        for (int d = 0; d <4; d++) {
            int ny = y + dy[d];
            int nx = x + dx[d];

            if (0 <= ny && ny < R && 0 <= nx && nx < C && current[ny][nx] != -1) {
                next[ny][nx] += spreadAmount;
                next[y][x] -= spreadAmount;
            }
        }
    }
}