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

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

package implement;

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

public class Impl17144 {

    static int R;

    static int C;

    static int T;

    static int[][] room;


    static int uaX;
    static int uaY;
    static int baX;
    static int baY;


    // 북 동 남 서
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};

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

        boolean mFlag = false;
        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 && !mFlag) {
                    uaX = i;
                    uaY = j;
                    baX = i + 1;
                    baY = j;
                    mFlag = true;
                }
            }
        }
        for (int i = 0; i < T; i++) {
            slove();
        }

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

        }
        System.out.println(result);

    }

    private static void slove() {
        // 1단계
        Queue<int[]> mungiData = new LinkedList<>();
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (room[i][j] <= 0) continue;
                dataMungi(i, j, mungiData);
            }
        }
        if (!mungiData.isEmpty()) {
            dirMungi(mungiData);
        }

        // 2단계
        switchOn();

    }

    private static void dataMungi(int x, int y, Queue<int[]> mungiData) {
        for (int dir = 0; dir < 4; dir++) {
            int nextX = x + dx[dir];
            int nextY = y + dy[dir];

            if (nextX < 0 || nextX >= R || nextY < 0 || nextY >= C) continue;
            if (room[nextX][nextY] == -1) continue;
            mungiData.add(new int[]{nextX, nextY, x, y});
        }
    }

    private static void dirMungi(Queue<int[]> mungiData) {
        int[][] tempRoom = new int[R][C];
        int[] temp = mungiData.peek();
        int coreX = temp[2];
        int coreY = temp[3];
        int size = 0;
        int core = room[temp[2]][temp[3]] / 5;

        while (!mungiData.isEmpty()) {
            int[] poll = mungiData.poll();
            if (coreX == poll[2] && coreY == poll[3]) {
                size++;
            } else {
                room[coreX][coreY] = room[coreX][coreY] - core * size;

                size = 1;
                coreX = poll[2];
                coreY = poll[3];
                core = room[coreX][coreY] / 5;
            }
            if (core == 0) continue;
            tempRoom[poll[0]][poll[1]] += core;

        }

        // 마지막 원소 바꿔주기
        room[coreX][coreY] = room[coreX][coreY] - core * size;

        // 종자는 원본 배열에 그대로 넣어도 무방
        // 단 종자가 퍼뜨린 먼지양은 temp에 저장해서 다음 순서에도 지장없게 해야됨
        // 따라서 마지막에 합치자

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (room[i][j] == -1) continue;
                room[i][j] += tempRoom[i][j];

            }
        }


    }

    private static void switchOn() {

        int uDir = 0;
        int bDir = 2;
        int nuX = uaX + dx[uDir];
        int nuY = uaY + dy[uDir];
        int nbX = baX + dx[bDir];
        int nbY = baY + dy[bDir];

        while (true) {
            // 위 반시계 북 동 남 서
            nuX += dx[uDir];
            nuY += dy[uDir];

            if (nuX < 0 || nuX >= R || nuY < 0 || nuY >= C) {
                nuX -= dx[uDir];
                nuY -= dy[uDir];
                uDir = uDir + 1 >= 4 ? 0 : uDir + 1;
                nuX += dx[uDir];
                nuY += dy[uDir];
            }

            if (room[nuX][nuY] == -1) {
                room[nuX - dx[uDir]][nuY - dy[uDir]] = 0;
                break;
            }
            room[nuX - dx[uDir]][nuY - dy[uDir]] = room[nuX][nuY];
            if (nuX == uaX) {
                uDir = 3;
            }

        }

        while (true) {
            // 아래 시계 남 동 북 서
            nbX += dx[bDir];
            nbY += dy[bDir];

            if (nbX < 0 || nbX >= R || nbY < 0 || nbY >= C) {

                nbX -= dx[bDir];
                nbY -= dy[bDir];
                bDir = bDir - 1 < 0 ? 3 : bDir - 1;
                nbX += dx[bDir];
                nbY += dy[bDir];

            }
            if (room[nbX][nbY] == -1) {
                room[nbX - dx[bDir]][nbY - dy[bDir]] = 0;
                break;
            }

            room[nbX - dx[bDir]][nbY - dy[bDir]] = room[nbX][nbY];
            if (nbX == baX) {
                bDir = 3;
            }
        }
    }
}

 

문제 자체는 이해가 정말 쉬웠는데, 구현 과정이 꽤 복잡해서 3시간이나 잡아먹혔다. 실수도 많이 했다.

1. 저번에 풀었던 아기상어 문제와 조금 비슷한 부분이 있었는데, 먼지가 동시에 퍼진다는 것을 인지하지 못하고 각각 개별적으로 퍼뜨렸다. 결국 temp 배열을 만들어서 해결했다.
2. 공기청정기 순환 방향도 위와 아래를 모두 1바퀴씩 돌게 구현했었는데, x좌표를 활용해서 해당 열까지만 돌게 하여 해결했다.
3. 다 해결된 줄 알았는데, 답이 이상하게 나왔다. 살펴보니 coreX와 coreY가 갱신되지 않아서 한 먼지 종자만 계속 값이 바뀌어 이상하게 계산되었다. 결국 else문일 때 core 좌표를 업데이트해줘서 해결했다.
4. 마지막으로 visit 배열 문제였다. visit 배열은 먼지가 있으면 true로 표시되는데, 공기청정기가 지나가면 같이 값이 바뀌어야 하는데 그렇지 않았다. 이 부분을 2시간이나 들여다봤다. 사실상 1시간 만에 풀 수 있는 문제였는데... 아쉽다. 그래서 결국 먼지가 있는 칸(>0)만 탐색하도록 고쳐서 해결했다.

다음 주 삼성메디슨 시험인데, 이번 실수를 발판 삼아 잘 준비해봐야겠다.