17144번. 미세먼지 안녕!

 

 

아이디어

문제는 되게 길어보이지만 결국 정리하자면 정해진 시간 동안

 

1. 확산

2. 공기청정

 

과정을 수행하고 마지막에 남은 먼지 양을 체크하는 문제이다.

 

공기청정 과정은 배열에 담긴 값을 한 칸씩 밀면 되는 단순한 단계이고 약간 머리를 써야 하는 부분은 '확산' 이다.

 

'확산'은 현 시점에서 먼지가 있는 모든 위치에서 동시에 일어나야 하므로 배열 하나만 사용할 경우 현 시점에 확산된 먼지가 동일한 시점에 재확산 되는 현상이 발생한다

 

따라서 '확산' 시에는 임시 배열을 만들어 임시 배열로 확산을 수행해야 한다.

 

 

풀이코드

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

public class Main {

    static int R;
    static int C;
    static List<Integer> airCleaner = new ArrayList<>();

    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());
        int T = Integer.parseInt(st.nextToken());

        int[][] room = new int[R][C];
        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) airCleaner.add(i);
            }
        }

        while (T > 0) {
            diffusion(room);
            runAirCleaner(room);
            T--;
        }

        System.out.println(sumOfDust(room));
    }

    public static void diffusion(int[][] room) {
        int[][] newRoom = new int[R][C];
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        for (int x = 0; x < R; x++) {
            for (int y = 0; y < C; y++) {
                if (room[x][y] > 0) {
                    int cnt = 0;
                    for (int i = 0; i < 4; i++) {
                        int nx = x + dx[i];
                        int ny = y + dy[i];

                        if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
                        if (room[nx][ny] == -1) continue;

                        newRoom[nx][ny] += (room[x][y] / 5);
                        cnt++;
                    }

                    room[x][y] -= (cnt * (room[x][y] / 5));
                }
            }
        }

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

    public static void runAirCleaner(int[][] room) {
        int upper = airCleaner.get(0);
        int lower = airCleaner.get(1);
        // 위쪽
        for (int i = upper - 1; i > 0; i--) {
            room[i][0] = room[i - 1][0];
        }

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

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

        for (int j = C - 1; j > 0; j--) {
            room[upper][j] = room[upper][j - 1];
            if (j == 1) room[upper][j] = 0;
        }

        // 아래쪽
        for (int i = lower + 1; i < R - 1; i++) {
            room[i][0] = room[i + 1][0];
        }

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

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

        for (int j = C - 1; j > 0; j--) {
            room[lower][j] = room[lower][j - 1];
            if (j == 1) room[lower][j] = 0;
        }
    }

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

        return result;
    }
}