BOJ 17144 : 미세먼지 안녕

문제링크

풀이요약

구현

풀이상세

1. 문제 풀이에 적혀있는대로 해야할 일을 구분하자.

   • 미세먼지 확산시키기
   • 공기청정기 작동

2. 미세 먼지 확산의 경우, 먼저 4방향을 통한 확산시 좌표의 변경값을 저장하는 이차원 배열 u_map 을 따로 만든다. 현재 초에서 모든 맵에 존재하는 미세먼지의 확산이 완료된 경우에 최종 변경 내역을 map 에 반영한다. map += u_map

3. 공기청정기 바람은 배열의 총 테두리에만 그것도, 항상 동일한 좌표에만 움직이고 있다. 이 말은 즉, 좌표를 미리 저장해두고, 각 좌표마다 +1 칸씩 이동하도록 만드는 것이 가능하다.

4. 처음 input 값을 반영할 때, 각 공기청정기 위의 바람과 아래의 바람에 영향을 받는 좌표를 모두 구한다. 해당 좌표를 구하는 방법은 공기청정기가 처음 등장하는 경우는 무조건 위쪽 부터이니, 위쪽 바람에서는 오른쪽, 위쪽, 왼쪽, 아래쪽 순으로 훝고, 아래쪽 바람에서는 오른쪽, 아래쪽, 왼쪽, 위쪽으로 훝어 좌표를 구한다.

5. 매 시간 초마다, 미세먼지 확산 함수와, 공기청정기 위,아래 바람 이동 함수를 작동시킨다.

6. 모든 시간이 경과되었다면, 현재 map 좌표에 0 보다 큰 값을 모두 더한다.

import java.io.*;
import java.util.*;

public class Main {
    static int R, C, T;
    static int map[][], u_map[][];
    static List<int[]> u_pos, d_pos;
    static int[][] uw = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};
    static int[][] dw = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    private static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
        R = Integer.parseInt(stk.nextToken());
        C = Integer.parseInt(stk.nextToken());
        T = Integer.parseInt(stk.nextToken());
        map = new int[R][C];
        u_map = new int[R][C];

        boolean check = false;
        for (int i = 0; i < R; i++) {
            stk = new StringTokenizer(br.readLine());
            for (int j = 0; j < C; j++) {
                map[i][j] = Integer.parseInt(stk.nextToken());
                if (map[i][j] == -1) {
                    if (!check) {
                        u_pos = find_pos(new int[]{i, j}, uw);
                        check = true;
                    } else d_pos = find_pos(new int[]{i, j}, dw);
                }
            }
        }
    }

    private static List<int[]> find_pos(int[] c, int[][] dd) {
        int cnt = 0;
        int[] curr = new int[]{c[0], c[1]};
        List<int[]> list = new ArrayList<>();
        while (true) {
            int nr = curr[0] + dd[cnt][0];
            int nc = curr[1] + dd[cnt][1];
            if (nr == c[0] && nc == c[1]) break;
            if (nr < 0 || nc < 0 || nr >= R || nc >= C) {
                cnt++;
                continue;
            }
            curr = new int[]{nr, nc};
            list.add(new int[]{nr, nc});
        }
        return list;
    }

    private static void go() {
        // 미세먼지 확산
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                if (map[r][c] > 0 && map[r][c] / 5 > 0) {
                    int cnt = 0;
                    for (int d = 0; d < 4; d++) {
                        int dr = r + uw[d][0];
                        int dc = c + uw[d][1];
                        if (dr < 0 || dc < 0 || dr >= R || dc >= C) continue;
                        if (map[dr][dc] == -1) continue;
                        u_map[dr][dc] += (map[r][c] / 5);
                        cnt++;
                    }
                    u_map[r][c] -= (cnt * (map[r][c] / 5));
                }
            }
        }

        // 변경사항 반영
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                if (u_map[r][c] != 0) {
                    map[r][c] += u_map[r][c];
                    u_map[r][c] = 0;
                }
            }
        }
    }

    private static void move(List<int[]> pos) {
        for (int i = pos.size()-1; i > 0; i--) {
            map[pos.get(i)[0]][pos.get(i)[1]] = map[pos.get(i - 1)[0]][pos.get(i - 1)[1]];
        }
        map[pos.get(0)[0]][pos.get(0)[1]] = 0;
    }

    private static void solve() {
        while (--T >= 0) {
            // 미세먼지 확산
            go();
            // 공기청정기 바람에 의한 미세먼지 이동
            move(u_pos);
            move(d_pos);
        }

    }

    private static void output() {
        int ans = 0;
        for(int i=0; i<R; i++) {
            for(int j=0; j<C; j++) {
                if(map[i][j]>0) ans+=map[i][j];
            }
        }
        System.out.println(ans);
    }

    public static void main(String[] args) throws Exception {
        input();
        solve();
        output();
    }
}