[백준 17144, Java] 미세먼지 안녕!

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

17144번: 미세먼지 안녕!

주어진 정보

• 미세먼지 확산
  • 미세먼지가 있는 모든 칸에서 동시에 일어난다.
  • 인접한 네 방향으로 확산된다.
  • 확산되는 양은 A[r][c] / 5이고 소수점은 버린다.
  • 남은 미세먼지의 양 = 기존 미세먼지의 양 - 확산되는 양 * 확산된 방향의 개수
• 공기청정기 작동
  • 공기청정기는 위쪽, 아래쪽이 존재한다.
  • 위쪽 공기청정기의 바람은 반시계방향, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
  • 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
  • 공기청정기에서 부는 바람은 미세먼지가 없다.
  • 공기청정기로 들어간 미세먼지는 기존의 미세먼지의 양에서 뺀다.

 

풀이 과정

이 문제는 미세먼지 확산, 공기청정기 작동 두 동작만 만들면 해결할 수 있다. 

미세먼지 확산

주어진 방과 같은 크기의 배열(empty)을 만들어, 확산된 미세먼지의 양을 할당하고 방의 미세먼지엔 확산된 만큼의 미세먼지 양을 뺀다. 확산된 모든 미세먼지의 양을 구하면 방에 그 값들을 더한다. 여기엔 방법이 두 가지가 있다. 

1. Deque에 먼지가 있는 칸의 좌표를 넣고, 먼지가 있는 칸만 탐색해 empty 배열에 확산된 미세먼지 양을 할당한다.
2. 방의 모든 좌표를 탐색해 empty 배열에 확산된 미세먼지 양을 할당한다. 

1번은 메모리를 더 사용하는 대신, 먼지가 있는 좌표만을 탐색하고 2번은 추가 메모리할당은 없지만 모든 좌표를 탐색한다. 1번의 메모리 사용량이 2번에 비해 2배 정도 높았기 때문에 2번 방법을 선택했다. 반면 시간은 크게 차이가 나지 않았는데, 그 이유는 공기청정기가 작동하고 이동한 먼지의 좌표를 다시 Deque에 넣어야 하고  추가적인 시간이 필요했기 때문이다. 

 

공기청정기 작동

공기청정기의 좌표에 따라 위쪽은 반시계방향 아래쪽은 시계방향으로 먼지를 옮기고, 공기청정기에 들어간 먼지를 반환하게 했다. 정화된 먼지를 dustSum에서 뺐다. 

 

미세먼지의 합 구하기

처음에는 Deque에 먼지가 있는 좌표를 넣는 방식을 사용했다. 하지만 먼지의 정보를 가지고 있으면서 마지막에 또 sum()이라는 함수를 사용해 미세먼지의 합을 구하는 것은 효율적이지 않았다. 미세먼지 확산에서 2번 방법을 선택하고 dustSum이란 변수를 사용해 공기청정기에서 정화된 먼지를 빼는 방식을 사용해 미세먼지의 합을 구했다. 이 방법이 더 적은 시간을 요구했다. 

 

처음 코드(Deque, sum() 사용)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int R, C, T;
    private static int[][] room;
    private static Deque<int[]> dust = new ArrayDeque<>();
    private static AirCleaner airCleaner = new AirCleaner();
    private static int[] dx = {1, 0, -1, 0};
    private static int[] dy = {0, 1, 0, -1};
    public static void main(String[] args) throws IOException {
        String[] input = br.readLine().split(" ");
        R = Integer.parseInt(input[0]);
        C = Integer.parseInt(input[1]);
        T = Integer.parseInt(input[2]);

        room = new int[R][C];

        for (int i = 0; i < R; i++) {
            input = br.readLine().split(" ");
            for (int j = 0; j < C; j++) {
                room[i][j] = Integer.parseInt(input[j]);
                if (room[i][j] == -1) {
                    airCleaner.setCleaner(i, j);
                }
                else if (room[i][j] != 0) {
                    dust.addFirst(new int[]{i, j});
                }
            }
        }

        for (int i = 0; i < T; i++) {
            diffusion();
            runCleaner();
        }
        System.out.println(sum());
    }

    public static void diffusion() {
        int[][] empty = new int[R][C];

        while(!dust.isEmpty()) {
            int[] current = dust.pollFirst();
            int temp = room[current[0]][current[1]] / 5;

            for (int i = 0; i < 4; i++) {
                int nx = current[0] + dx[i];
                int ny = current[1] + dy[i];

                if (OOB(nx, ny) || nearby(nx, ny)) continue;
                room[current[0]][current[1]] -= temp;
                empty[nx][ny] += temp;
            }
        }

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

    public static void runCleaner() {
        for (int i = airCleaner.front[0] - 2; i > -1; i--) {
            room[i + 1][0] = room[i][0];
        }

        for (int i = 1; i < C; i++) {
            room[0][i - 1] = room[0][i];
        }

        for (int i = 1; i < airCleaner.front[0] + 1; i++) {
            room[i - 1][C - 1] = room[i][C - 1];
        }

        for (int i = C - 2; i > 0; i--) {
            room[airCleaner.front[0]][i + 1] = room[airCleaner.front[0]][i];
        }

        room[airCleaner.front[0]][1] = 0;

        for (int i = airCleaner.rear[0] + 2; i < R; i++) {
            room[i - 1][0] = room[i][0];
        }

        for (int i = 1; i < C; i++) {
            room[R - 1][i - 1] = room[R - 1][i];
        }

        for (int i = R - 2; i > airCleaner.rear[0] - 1; i--) {
            room[i + 1][C - 1] = room[i][C - 1];
        }

        for (int i = C - 2; i > 0; i--) {
            room[airCleaner.rear[0]][i + 1] = room[airCleaner.rear[0]][i];
        }

        room[airCleaner.rear[0]][1] = 0;

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (room[i][j] > 0) {
                    dust.add(new int[]{i, j});
                }
            }
        }
    }

    private static boolean OOB(int x, int y) {
        return x < 0 || x > R - 1 || y < 0 || y > C - 1;
    }

    private static boolean nearby(int x, int y) {
        if (x == airCleaner.front[0] && y == airCleaner.front[1]) return true;
        if (x == airCleaner.rear[0] && y == airCleaner.rear[1]) return true;

        return false;
    }
    public static int sum() {
        int sum = 0;
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (room[i][j] != -1) sum += room[i][j];
            }
        }

        return sum;
    }

    static class AirCleaner{
        private int[] front;
        private int[] rear;

        public void setCleaner(int x, int y) {
            if (front == null) {
                front = new int[2];
                front[0] = x;
                front[1] = y;
            } else {
                rear = new int[2];
                rear[0] = x;
                rear[1] = y;
            }
        }
    }
}

 

개선한 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int R, C, T;
    private static int[][] room, newRoom, tmpRoom;
    private static AirCleaner airCleaner = new AirCleaner();
    private static int dustSum = 0;
    private static int[] dx = {1, 0, -1, 0};
    private static int[] dy = {0, 1, 0, -1};
    public static void main(String[] args) throws IOException {
        String[] input = br.readLine().split(" ");
        R = Integer.parseInt(input[0]);
        C = Integer.parseInt(input[1]);
        T = Integer.parseInt(input[2]);

        room = new int[R][C];

        for (int i = 0; i < R; i++) {
            input = br.readLine().split(" ");
            for (int j = 0; j < C; j++) {
                room[i][j] = Integer.parseInt(input[j]);
                if (room[i][j] == -1) {
                    airCleaner.setCleaner(i, j);
                }
                else if (room[i][j] != 0) {
                    dustSum += room[i][j];
                }
            }
        }

        for (int i = 0; i < T; i++) {
            diffusion();
            dustSum -= runCleaner();
        }
        System.out.println(dustSum);
    }

    public static void diffusion() {
        newRoom = new int[R][C];

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                int remainingDust = room[i][j];
                int spreadingDust = remainingDust / 5;

                for (int k = 0; k < 4; k++) {
                    int nx = i + dx[k];
                    int ny = j + dy[k];

                    if (OOB(nx, ny) || nearby(nx, ny)) continue;
                    newRoom[nx][ny] += spreadingDust;
                    remainingDust -= spreadingDust;
                }

                newRoom[i][j] += remainingDust;
                room[i][j] = 0;
            }
        }

        tmpRoom = room;
        room = newRoom;
        newRoom = tmpRoom;
        tmpRoom = null;
    }

    public static int runCleaner() {
        int dust = room[airCleaner.front[0] - 1][0] + room[airCleaner.rear[0] + 1][0];

        for (int i = airCleaner.front[0] - 2; i > -1; i--) {
            room[i + 1][0] = room[i][0];
        }

        for (int i = 1; i < C; i++) {
            room[0][i - 1] = room[0][i];
        }

        for (int i = 1; i < airCleaner.front[0] + 1; i++) {
            room[i - 1][C - 1] = room[i][C - 1];
        }

        for (int i = C - 2; i > 0; i--) {
            room[airCleaner.front[0]][i + 1] = room[airCleaner.front[0]][i];
        }

        room[airCleaner.front[0]][1] = 0;

        for (int i = airCleaner.rear[0] + 2; i < R; i++) {
            room[i - 1][0] = room[i][0];
        }

        for (int i = 1; i < C; i++) {
            room[R - 1][i - 1] = room[R - 1][i];
        }

        for (int i = R - 2; i > airCleaner.rear[0] - 1; i--) {
            room[i + 1][C - 1] = room[i][C - 1];
        }

        for (int i = C - 2; i > 0; i--) {
            room[airCleaner.rear[0]][i + 1] = room[airCleaner.rear[0]][i];
        }

        room[airCleaner.rear[0]][1] = 0;

        return dust;
    }

    private static boolean OOB(int x, int y) {
        return x < 0 || x > R - 1 || y < 0 || y > C - 1;
    }

    private static boolean nearby(int x, int y) {
        if (x == airCleaner.front[0] && y == airCleaner.front[1]) return true;
        if (x == airCleaner.rear[0] && y == airCleaner.rear[1]) return true;

        return false;
    }

    static class AirCleaner{
        private int[] front;
        private int[] rear;

        public void setCleaner(int x, int y) {
            if (front == null) {
                front = new int[2];
                front[0] = x;
                front[1] = y;
            } else {
                rear = new int[2];
                rear[0] = x;
                rear[1] = y;
            }
        }
    }
}