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

문제 이해

 

• 방 안에 먼지와 두 대의 공기청정기가 있습니다.
• 먼지는 매 초마다 주변 네 방향으로 확산되며, 공기청정기는 일정한 방향으로 공기를 순환시켜 먼지를 제거합니다.
• 이 프로그램은 먼지가 확산되고, 청정기가 작동하는 과정을 반복해 t초 후 방에 남은 먼지의 양을 계산합니다.

 

 

핵심 아이디어

 

1. 먼지 확산:
   • 각 먼지 칸은 자신의 양의 1/5을 상하좌우로 확산시킵니다.
   • 확산된 먼지는 원래 있던 양에서 차감되며, 벽이나 공기청정기 칸으로는 확산되지 않습니다.
2. 공기청정기 작동:
   • 두 대의 공기청정기가 반대 방향으로 바람을 순환시켜 먼지를 제거합니다.
   • 윗쪽 청정기는 반시계 방향으로, 아랫쪽 청정기는 시계 방향으로 공기를 순환시킵니다.
   • 청정기를 지나간 칸의 먼지는 0으로 초기화됩니다.

 

 

알고리즘 흐름

 

• 초기화 단계: 방의 크기와 먼지의 초기 상태, 청정기의 위치를 설정합니다.
• t초 동안 반복:
  • 먼지 확산: 매 초마다 모든 먼지가 상하좌우로 확산됩니다.
  • 청정기 작동: 두 청정기가 각각 먼지를 순환시키고 제거합니다.
• 최종 먼지 계산: t초 후 남은 먼지의 총량을 구합니다.

 

---

정답은 더보기 클릭

import java.util.*;

class Main {
    // 방의 크기 및 시간 정보
    static int r, c, t;
    static int[][] floor;         // 현재 방의 먼지 상태
    static int[][] spreadFloor;   // 확산된 먼지 상태 저장 배열

    // 공기청정기의 위치
    static int robotR = -1;  // 로봇(공기청정기)의 상단 위치 행
    static int robotC = -1;  // 로봇의 열 위치

    // 확산 방향 (상, 하, 좌, 우)
    static int[] dr = {1, -1, 0, 0};
    static int[] dc = {0, 0, 1, -1};

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        // 방의 행, 열, 실행 시간 입력
        r = in.nextInt();
        c = in.nextInt();
        t = in.nextInt();
        in.nextLine();

        // 초기 방 상태 설정
        initFloor(in);

        // t초 동안 확산과 정화 반복
        for (int i = 0; i < t; i++) {
            spread();  // 먼지 확산
            blowing(); // 공기청정기 작동
        }

        // 최종 남은 미세먼지 양 출력 (공기청정기 위치의 -2를 제외하기 위해 +2)
        System.out.println(getFineDust() + 2);
    }

    // 공기청정기 작동 로직
    public static void blowing() {
        // 상단 청정기: 반시계 방향 바람 이동
        for (int i = robotR - 1; i >= 0; i--) {
            if (floor[i + 1][0] == -1) continue;  // 청정기 위치는 건너뜀
            floor[i + 1][0] = floor[i][0];  // 아래로 이동
        }
        for (int i = 1; i < c; i++) {
            floor[0][i - 1] = floor[0][i];  // 오른쪽으로 이동
        }
        for (int i = 1; i <= robotR; i++) {
            floor[i - 1][c - 1] = floor[i][c - 1];  // 위로 이동
        }
        for (int i = c - 2; i >= 1; i--) {
            floor[robotR][i + 1] = floor[robotR][i];  // 왼쪽으로 이동
        }
        floor[robotR][1] = 0;  // 청정기 옆은 먼지가 없도록 초기화

        // 하단 청정기: 시계 방향 바람 이동
        robotR++;  // 하단 청정기 위치로 이동
        for (int i = robotR + 1; i < r; i++) {
            if (floor[i - 1][0] == -1) continue;  // 청정기 위치는 건너뜀
            floor[i - 1][0] = floor[i][0];  // 위로 이동
        }
        for (int i = 1; i < c; i++) {
            floor[r - 1][i - 1] = floor[r - 1][i];  // 왼쪽으로 이동
        }
        for (int i = r - 2; i >= robotR; i--) {
            floor[i + 1][c - 1] = floor[i][c - 1];  // 아래로 이동
        }
        for (int i = c - 2; i >= 1; i--) {
            floor[robotR][i + 1] = floor[robotR][i];  // 오른쪽으로 이동
        }
        floor[robotR][1] = 0;  // 청정기 옆은 먼지가 없도록 초기화

        robotR--;  // 상단 청정기 위치로 되돌림
    }

    // 미세먼지 확산 로직
    public static void spread() {
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (floor[i][j] <= 0) continue;  // 먼지가 없거나 공기청정기 위치일 때

                int count = spreadCount(i, j);  // 확산 가능한 방향 수 계산
                floor[i][j] -= (floor[i][j] / 5) * count;  // 남은 먼지 계산
            }
        }

        // 확산된 먼지 상태를 원래 방 상태로 반영
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                floor[i][j] += spreadFloor[i][j];
                spreadFloor[i][j] = 0;  // 확산 배열 초기화
            }
        }
    }

    // 확산 가능 방향과 양 계산
    public static int spreadCount(int i, int j) {
        int count = 0;

        for (int k = 0; k < 4; k++) {
            int nr = i + dr[k];
            int nc = j + dc[k];

            // 범위를 벗어나지 않고, 공기청정기가 아닌 경우
            if (nr >= 0 && nc >= 0 && nr < r && nc < c 
                && !((nr == robotR || nr == robotR + 1) && nc == robotC)) {
                count++;
                spreadFloor[nr][nc] += floor[i][j] / 5;  // 확산된 먼지 저장
            }
        }

        return count;
    }

    // 초기 방 상태 설정
    public static void initFloor(Scanner in) {
        floor = new int[r][c];
        spreadFloor = new int[r][c];

        for (int i = 0; i < r; i++) {
            String[] tmp = in.nextLine().split(" ");
            for (int j = 0; j < c; j++) {
                int el = Integer.parseInt(tmp[j]);
                if (el == -1 && robotR == -1) {
                    robotR = i;  // 공기청정기 상단 위치 설정
                    robotC = j;
                }
                floor[i][j] = el;
            }
        }
    }

    // 전체 미세먼지 양 계산
    public static int getFineDust() {
        int result = 0;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                result += floor[i][j];  // 모든 먼지의 합 계산
            }
        }
        return result;
    }

    // 디버깅용 출력 함수
    public static void print() {
        for (int[] arr : floor) {
            System.out.println(Arrays.toString(arr));
        }
        System.out.println("----------------");
        for (int[] arr : spreadFloor) {
            System.out.println(Arrays.toString(arr));
        }
    }
}