백준 - 17144번(미세먼지 안녕!)

문제 출처: https://www.acmicpc.net/problem/17144

---

문제

• 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.

• 공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.

• 1초 동안 아래 적힌 일이 순서대로 일어난다.

1. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.

   • (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
   • 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
   • 확산되는 양은 Ar,c/5이고 소수점은 버린다.
   • (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.
   • 공기청정기가 작동한다.

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

   • 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
   • 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
   • 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.

다음은 확산의 예시이다.

왼쪽과 오른쪽에 칸이 없기 때문에, 두 방향으로만 확산이 일어났다.

인접한 네 방향으로 모두 확산이 일어난다.

공기청정기가 있는 칸으로는 확산이 일어나지 않는다.

공기청정기의 바람은 다음과 같은 방향으로 순환한다.

방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.

---

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

public class Main {

    // 0 ~ 3 -> 위쪽 공기청정기, 4 ~ 7 -> 아래쪽 공기청정기
    private static int[][] directions = {
            { -1, 0 },  // 상
            { 0, 1 },   // 우
            { 1, 0 },   // 하
            { 0, -1 },  // 좌
            { 1, 0 },   // 하
            { 0, 1 },   // 우
            { -1, 0 },  // 상
            { 0, -1 },  // 좌
    };

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int R = Integer.parseInt(tokenizer.nextToken()); // 행
        int C = Integer.parseInt(tokenizer.nextToken()); // 열
        int T = Integer.parseInt(tokenizer.nextToken()); // 초

        int air = 0; // 최종적으로 두 행 중 밑의 행을 가리키게 됨. (air - 1, air) 두 행에 공기청정기 위치

        // 배열 채우기
        int[][] pm = new int[R][C];
        for (int i = 0; i < R; i++) {
            tokenizer = new StringTokenizer(reader.readLine());
            for (int j = 0; j < C; j++) {
                pm[i][j] = Integer.parseInt(tokenizer.nextToken());
                if (pm[i][j] == -1) air = i;
            }
        }

        for (int i = 0; i < T; i++) {
            pm = spread(pm, R, C); // -> T초동안 반복해야됨
            purify(pm, air - 1, air, R, C);
        }

        int sum = 0;

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                sum += pm[i][j];
            }
        }

        System.out.println(sum + 2);
    }

    // 공기청정기 돌리기
    private static void purify(int[][] pm, int up, int down, int R, int C) {
        // 위쪽 돌리기
        // 시작점 세팅
        int dy = up - 1;
        int dx = 0;

        int index = 0;

        while (true) {
            dy += directions[index][0];
            dx += directions[index][1];

            if (dy == up && dx == 0) break; // 공기청정기에 닿았을 경우

            // 유효 인덱스 범위일 경우
            if (dy >= 0 && dy <= up && dx >= 0 && dx < C) {
                pm[dy - directions[index][0]][dx - directions[index][1]] = pm[dy][dx];
            } else {
                dy -= directions[index][0];
                dx -= directions[index][1];
                index++;
            }
        }

        pm[up][1] = 0;

        // 아래쪽 돌리기
        // 시작점 세팅
        dy = down + 1;
        dx = 0;

        index = 4;

        while (true) {
            dy += directions[index][0];
            dx += directions[index][1];

            if (dy == down && dx == 0) break; // 공기청정기에 닿았을 경우

            // 유효 인덱스 범위일 경우
            if (dy >= down && dy < R && dx >= 0 && dx < C) {
                pm[dy - directions[index][0]][dx - directions[index][1]] = pm[dy][dx];
            } else {
                dy -= directions[index][0];
                dx -= directions[index][1];
                index++;
            }
        }

        pm[down][1] = 0;
    }

    // 미세먼지의 확산
    private static int[][] spread(int[][] pm, int R, int C) {
        int[][] copyPM = new int[R][C];
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                copyPM[i][j] = pm[i][j];
            }
        }

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (pm[i][j] > 0) {
                    int cnt = 0;
                    for (int k = 0; k < 4; k++) {
                        int dy = i + directions[k][0];
                        int dx = j + directions[k][1];

                        if (dy >= 0 && dy < R && dx >= 0 && dx < C && pm[dy][dx] != -1) {
                            copyPM[dy][dx] += pm[i][j] / 5; // 확산된 위치의 미세먼지 값 업데이트
                            cnt++;
                        }
                    }
                    copyPM[i][j] -= pm[i][j] / 5 * cnt; // 현재 위치의 미세먼지 값 업데이트
                }
            }
        }

        return copyPM;
    }

}

---

• 정확한 로직에 대한 생각없이 풀었다가 많은 시간이 걸린 문제다.
• 먼저 크게 2단계로 나눠진다. 미세먼지가 확산되는 단계와 공기청정기가 가동되는 단계이다.
• 미세먼지가 확산되는 단계는 각 미세먼지들이 동시에 확산되므로 배열을 하나 복사하여 원래의 값을 저장하는 배열과 변화된 값을 저장하는 배열을 두고 구현하였다.
• 원본 값 배열에서 미세먼지를 찾으면 4방을 탐색하여 미세먼지를 확산시키고, 확산시킨 값은 복사된 배열에 저장하여 새로 나온 미세먼지를 또 탐색하는 경우를 방지하였다.
• 최종적으로는 값이 변경된(복사된) 배열을 반환하여 배열을 업데이트하였다.
• 미세먼지가 확산된 다음에는 공기청정기를 가동시킨다. 공기청정기는 0열에 고정되므로 행의 위치를 2개 구하여 공기청정기의 위치를 구한다.
• 공기청정기의 위쪽과 아래쪽의 방향이 다르다. 먼저 위쪽 부분은 반시계 방향으로 밀어지기 때문에 이를 처리하였고, 아래쪽은 시계방향으로 밀어지기 때문에 또 이를 처리하였다.
• 배열의 원소를 이동하는 것은 전에 연습하였으나 다시 하려니 쉽지 않았다. 핵심은 돌아가는 방향 반대 방향으로 진행하면 쉽게 구현할 수 있다는 것이다.