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

문제 링크

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

풀이 과정

시뮬레이션 문제입니다.

for (int i = 0; i < R; i++) {
    for (int j = 0; j < C; j++) {
        map[i][j] = sc.nextInt();

        if (map[i][j] == 0) continue;
        else if (map[i][j] == -1) airpurifier.add(new Point(i, j));
        else dust.add(new Point(i, j));
    }
}

먼저 문제의 입력을 받습니다.

• -1이면 공기청정기가 있는 위치이므로, airpurifier 라는 리스트에 해당 좌표를 추가해줍니다.
• 1이상이면 미세먼지가 있는 위치이므로, dust 라는 큐에 해당 좌표를 추가해줍니다.

int t = 0;

while (t < T) {
    t++;
    expand();
    rotate();
}

다음으로는 시간을 의미하는 t를 증가시키며, 미세먼지를 확산시키는 expand 메소드 와 공기청정기로 회전시키는 rotate 메소드 를 순서대로 호출합니다.

static void expand() {
    int[][] tmp = new int[R][C];
    for (int i = 0; i < R; i++)
        System.arraycopy(map[i], 0, tmp[i], 0, C);

    while (!dust.isEmpty()) {
        Point now = dust.poll();
        int delta = map[now.x][now.y] / 5;

        if (delta == 0) continue;

        for (int d = 0; d < 4; d++) {
            int nx = now.x + dx[d], ny = now.y + dy[d];

            if (!inRange(nx, ny) || map[nx][ny] == -1) continue;

            tmp[nx][ny] += delta;
            tmp[now.x][now.y] -= delta;
        }
    }

    map = tmp;
}

expand 메소드 는 미세먼지를 확산시킵니다. 모든 먼지가 한 번에 확산되어야 하므로 큐를 이용합니다.

1. 먼저, map 을 복사한 배열을 하나 만들어둡니다.
2. 큐에서 하나씩 제거하며, 해당 위치 상하좌우 인접한 네 곳을 확인합니다.
3. 범위 밖이 아니거나, 공기청정기가 위치하지 않는다면, 문제 규칙에 따라 확산을 진행해줍니다.
4. 확산이 끝나면, map 이 복사한 배열을 가리키게 해줍니다.

static void rotate() {
    Point airpurifierUp = airpurifier.get(0);
    Point airpurifierDown = airpurifier.get(1);

    for (int i = airpurifierUp.x; i >= 1; i--) map[i][0] = map[i - 1][0];
    for (int j = 0; j < C - 1; j++) map[0][j] = map[0][j + 1];
    for (int i = 0; i < airpurifierUp.x; i++) map[i][C - 1] = map[i + 1][C - 1];
    for (int j = C - 1; j >= 1; j--) map[airpurifierUp.x][j] = map[airpurifierUp.x][j - 1];

    map[airpurifierUp.x][airpurifierUp.y] = -1;
    map[airpurifierUp.x][airpurifierUp.y + 1] = 0;

    for (int i = airpurifierDown.x; i < R - 1; i++) map[i][0] = map[i + 1][0];
    for (int j = 0; j < C - 1; j++) map[R - 1][j] = map[R - 1][j + 1];
    for (int i = R - 1; i > airpurifierDown.x; i--) map[i][C - 1] = map[i - 1][C - 1];
    for (int j = C - 1; j >= 1; j--) map[airpurifierDown.x][j] = map[airpurifierDown.x][j - 1];

    map[airpurifierDown.x][airpurifierDown.y] = -1;
    map[airpurifierDown.x][airpurifierDown.y + 1] = 0;

    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
            if (map[i][j] > 0) dust.add(new Point(i, j));
}

rotate 메소드는 공기청정기의 진행 방향으로 미세먼지를 한 칸씩 이동시킵니다.

• 공기청정기의 윗 칸은 반시계 방향으로 먼지를 회전합니다. 위 사진 기준, 1 → 2→ 3→ 4 순서대로 한 칸씩 이동시킵니다.
• 공기청정기의 윗 칸은 시계 방향으로 먼지를 회전합니다. 위 사진 기준, 5 → 6 → 7 → 8 순서대로 한 칸씩 이동시킵니다.

코드

import java.awt.*;
import java.util.*;
import java.util.List;

public class Main {
    static int R, C, T;
    static int[][] map;
    static List<Point> airpurifier;
    static Queue<Point> dust;
    static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        R = sc.nextInt();
        C = sc.nextInt();
        T = sc.nextInt();
        map = new int[R][C];
        airpurifier = new ArrayList<>();
        dust = new LinkedList<>();

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                map[i][j] = sc.nextInt();

                if (map[i][j] == 0) continue;
                else if (map[i][j] == -1) airpurifier.add(new Point(i, j));
                else dust.add(new Point(i, j));
            }
        }

        int t = 0;

        while (t < T) {
            t++;
            expand();
            rotate();
        }

        int answer = 0;
        for (int i = 0; i < R; i++)
            for (int j = 0; j < C; j++)
                if (map[i][j] > 0) answer += map[i][j];

        System.out.println(answer);
    }

    static void expand() {
        int[][] tmp = new int[R][C];
        for (int i = 0; i < R; i++)
            System.arraycopy(map[i], 0, tmp[i], 0, C);

        while (!dust.isEmpty()) {
            Point now = dust.poll();
            int delta = map[now.x][now.y] / 5;

            if (delta == 0) continue;

            for (int d = 0; d < 4; d++) {
                int nx = now.x + dx[d], ny = now.y + dy[d];

                if (!inRange(nx, ny) || map[nx][ny] == -1) continue;

                tmp[nx][ny] += delta;
                tmp[now.x][now.y] -= delta;
            }
        }

        map = tmp;
    }

    static void rotate() {
        Point airpurifierUp = airpurifier.get(0);
        Point airpurifierDown = airpurifier.get(1);

        for (int i = airpurifierUp.x; i >= 1; i--) map[i][0] = map[i - 1][0];
        for (int j = 0; j < C - 1; j++) map[0][j] = map[0][j + 1];
        for (int i = 0; i < airpurifierUp.x; i++) map[i][C - 1] = map[i + 1][C - 1];
        for (int j = C - 1; j >= 1; j--) map[airpurifierUp.x][j] = map[airpurifierUp.x][j - 1];

        map[airpurifierUp.x][airpurifierUp.y] = -1;
        map[airpurifierUp.x][airpurifierUp.y + 1] = 0;

        for (int i = airpurifierDown.x; i < R - 1; i++) map[i][0] = map[i + 1][0];
        for (int j = 0; j < C - 1; j++) map[R - 1][j] = map[R - 1][j + 1];
        for (int i = R - 1; i > airpurifierDown.x; i--) map[i][C - 1] = map[i - 1][C - 1];
        for (int j = C - 1; j >= 1; j--) map[airpurifierDown.x][j] = map[airpurifierDown.x][j - 1];

        map[airpurifierDown.x][airpurifierDown.y] = -1;
        map[airpurifierDown.x][airpurifierDown.y + 1] = 0;

        for (int i = 0; i < R; i++)
            for (int j = 0; j < C; j++)
                if (map[i][j] > 0) dust.add(new Point(i, j));
    }

    static boolean inRange(int x, int y) {
        if (x < 0 || x > R - 1 || y < 0 || y > C - 1) return false;
        return true;
    }
}