백준: 17144번 (미세먼지) [JAVA]

문제 링크

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

17144번: 미세먼지 안녕!

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 문제에서 요구하는 대로 공기청정기를 통한 먼지의 이동 함수, 각 먼지들이 퍼지는 함수를 구현
2. 주어진 T초마다 이들을 반복 호출 후, 남은 먼지들의 총 합을 계산해 반환

 문제 해결을 위한 알고리즘 구현 난이도는 거의 없지만, 문제 자체에서 요구하는 로직 구현이 상당히 복잡하여 이들을 구현하는 것이 핵심인 문제이다.

 우선 문제에서도 보이다시피 초마다 움직임을 보이는 것은 먼지 자체의 퍼짐과 공기청정기가 있는 곳을 기준으로 위아래에 대해 크게 순환이다. 단순히 이 두 함수를 구현하고 나면 크게 어려울 것 없이 방에 대한 2차원 배열을 초기화하며 공기청정기의 위치와 각 먼지 양을 저장하고, 먼지가 존재하는 곳을 따로 큐에 저장한다.

 그 후에는 주어진 T초마다 변화에 대한 함수를 반복하면 된다. 한 번의 반복마다 기존의 먼지 위치와 양을 저장한 큐를 모두 돌며 해당 먼지들의 퍼짐을 계산하고 이후 공기청정기의 위쪽과 아래쪽의 순환을 돌게하고, 그렇게 함수의 반복을 끝내고 전체 2차원 배열을 다시 돌며 남은 먼지의 총합을 계산해 반환하면 된다.

 

public class Main {
    static int[][] room;
    static int[] airCleanerRow = new int[2];
    static int R, C, T;
    static Queue<Point> q = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int temp = 0, answer = 0;

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        T = Integer.parseInt(st.nextToken());

        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) {
                    airCleanerRow[temp++] = i;
                } else if (room[i][j] != 0) {
                    q.add(new Point(i, j, room[i][j]));
                }
            }
        }

        for (int i = 0; i < T; i++) {//주어진 초만큼 변화 반복
            change();
        }

        for (int i = 0; i < R; i++) {//방에 남은 미세먼지 양 모두 계산
            for (int j = 0; j < C; j++) {
                if (room[i][j] != 0 && room[i][j] != -1) {
                    answer += room[i][j];
                }
            }
        }

        System.out.println(answer);
    }

    static void change() {//한번의 순환
        while (!q.isEmpty()) {
            dirtMove(q.poll());
        }

        //공기청정기 위쪽 순환
        for (int r = airCleanerRow[0] - 1; r >= 1; r--) {
            room[r][0] = room[r - 1][0];
        }
        for (int c = 0; c < C - 1; c++) {
            room[0][c] = room[0][c + 1];
        }
        for (int r = 0; r < airCleanerRow[0]; r++) {
            room[r][C - 1] = room[r + 1][C - 1];
        }
        for (int c = C - 1; c > 1; c--) {
            room[airCleanerRow[0]][c] = room[airCleanerRow[0]][c - 1];
        }
        room[airCleanerRow[0]][1] = 0;

        //공기청정기 아래쪽 순환
        for (int r = airCleanerRow[1] + 1; r < R - 1; r++) {
            room[r][0] = room[r + 1][0];
        }
        for (int c = 0; c < C - 1; c++) {
            room[R - 1][c] = room[R - 1][c + 1];
        }
        for (int r = R - 1; r > airCleanerRow[1]; r--) {
            room[r][C - 1] = room[r - 1][C - 1];
        }
        for (int c = C - 1; c > 1; c--) {
            room[airCleanerRow[1]][c] = room[airCleanerRow[1]][c - 1];
        }
        room[airCleanerRow[1]][1] = 0;

        for (int i = 0; i < R; i++) {//다음 change() 함수에 사용할 먼지 좌표 큐 초기화
            for (int j = 0; j < C; j++) {
                if (room[i][j] != 0 && room[i][j] != -1) {
                    q.add(new Point(i, j, room[i][j]));
                }
            }
        }
    }

    static void dirtMove(Point p) {//퍼지는 먼지 계산
        int moveAmount = p.dirtAmount / 5, moveTotalAmount = 0;

        if (moveAmount == 0) {
            return;
        }

        if (p.c + 1 < C) {
            room[p.r][p.c + 1] += moveAmount;
            moveTotalAmount += moveAmount;
        }

        if (p.c - 1 >= 0 && room[p.r][p.c - 1] != -1) {
            room[p.r][p.c - 1] += moveAmount;
            moveTotalAmount += moveAmount;
        }

        if (p.r + 1 < R && room[p.r + 1][p.c] != -1) {
            room[p.r + 1][p.c] += moveAmount;
            moveTotalAmount += moveAmount;
        }

        if (p.r - 1 >= 0 && room[p.r - 1][p.c] != -1) {
            room[p.r - 1][p.c] += moveAmount;
            moveTotalAmount += moveAmount;
        }

        room[p.r][p.c] -= moveTotalAmount;
    }

    static class Point{
        int r, c, dirtAmount;

        public Point(int r, int c, int dirtAmount) {
            this.r = r;
            this.c = c;
            this.dirtAmount = dirtAmount;
        }
    }
}

결과