[Gold IV] 미세먼지 안녕! - 17144

문제 링크

성능 요약

메모리: 32064 KB, 시간: 316 ms

분류

구현, 시뮬레이션

문제 설명

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.

공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.

1초 동안 아래 적힌 일이 순서대로 일어난다.

  1. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
    • (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
    • 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
    • 확산되는 양은 Ar,c/5이고 소수점은 버린다. 즉, ⌊Ar,c/5⌋이다.
    • (r, c)에 남은 미세먼지의 양은 Ar,c - ⌊Ar,c/5⌋×(확산된 방향의 개수) 이다.
  2. 공기청정기가 작동한다.
    • 공기청정기에서는 바람이 나온다.
    • 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
    • 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
    • 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.

다음은 확산의 예시이다.

왼쪽과 위쪽에 칸이 없기 때문에, 두 방향으로만 확산이 일어났다.

인접한 네 방향으로 모두 확산이 일어난다.

공기청정기가 있는 칸으로는 확산이 일어나지 않는다.

공기청정기의 바람은 다음과 같은 방향으로 순환한다.

방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.

입력

첫째 줄에 R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000) 가 주어진다.

둘째 줄부터 R개의 줄에 Ar,c (-1 ≤ Ar,c ≤ 1,000)가 주어진다. 공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양이다. -1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.

 

코드 설명

변수 선언

• r, c: 방의 세로 크기(r)와 가로 크기(c).

• t: 시뮬레이션의 반복 횟수 (시간 t초).

• arr: 미세먼지와 공기청정기를 나타내는 r x c 배열.

• temp: 미세먼지 확산을 위해 사용하는 임시 배열.

• airCleanerTop, airCleanerBottom: 공기청정기의 위치. 위쪽과 아래쪽 공기청정기의 행 위치를 나타냄.

• dx, dy: 4방향(상, 하, 좌, 우) 이동을 위한 배열로, 미세먼지가 확산되는 방향을 처리하는 데 사용.

 

1. main 메소드

 입력 받기

• 방 크기와 시간, 방 상태를 입력받습니다.

• 공기청정기의 위치를 찾고, airCleanerTop과 airCleanerBottom에 저장합니다.

시뮬레이션 시작

• t번 반복하며 미세먼지 확산(spreadDust())과 공기청정기 작동(operateCleaner())을 시뮬레이션합니다.

 결과 출력

• getTotalDust()를 호출하여 공기청정기 외의 미세먼지 총합을 계산하고 출력합니다.

 

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());

    arr = new int[r][c];

    boolean found = false;
    for (int i = 0; i < r; i++) {
        st = new StringTokenizer(br.readLine());
        for (int j = 0; j < c; j++) {
            arr[i][j] = Integer.parseInt(st.nextToken());
            if (arr[i][j] == -1 && !found) {
                airCleanerTop = i;
                airCleanerBottom = i + 1;
                found = true;
            }
        }
    }

    while (t-- > 0) {
        spreadDust();
        operateCleaner();
    }

    System.out.println(getTotalDust());
}

 

2. spreadDust() 메소드

• 미세먼지 확산 시뮬레이션:

• arr 배열에서 각 칸에 있는 미세먼지를 확인하고, 그 미세먼지가 인접한 네 방향으로 확산됩니다.

• 확산되는 양은 원래 미세먼지 양의 1/5로, spreadAmount에 저장됩니다.

• 인접한 칸으로 미세먼지를 추가하고, 확산된 양만큼 원래 칸에서 감소시킵니다.

• 확산이 끝난 후 결과를 temp 배열에 저장하고, arr 배열을 갱신합니다.

이때 공기청정기의 위치는 arr[airCleanerTop][0]과 arr[airCleanerBottom][0]으로 표시되어 있으므로, 해당 위치는 미세먼지 확산에 영향을 받지 않도록 -1로 설정됩니다.

static void spreadDust() {
    temp = new int[r][c];
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (arr[i][j] > 0) {
                int spreadAmount = arr[i][j] / 5;
                int spreadCount = 0;

                for (int dir = 0; dir < 4; dir++) {
                    int nx = i + dx[dir];
                    int ny = j + dy[dir];

                    if (nx >= 0 && ny >= 0 && nx < r && ny < c && arr[nx][ny] != -1) {
                        temp[nx][ny] += spreadAmount;
                        spreadCount++;
                    }
                }
                temp[i][j] += arr[i][j] - (spreadAmount * spreadCount);
            }
        }
    }
    temp[airCleanerTop][0] = temp[airCleanerBottom][0] = -1;  // 공기청정기 위치 설정
    arr = temp;  // 확산된 결과를 arr에 반영
}

 

operateCleaner() 메소드

• 공기청정기 작동

• 위쪽 공기청정기( 반시계 방향)

• 공기청정기 상단에서 공기를 위로 밀고, 왼쪽, 아래쪽, 오른쪽으로 순차적으로 이동시킵니다.

• 각 방향으로 밀고 나면 공기청정기 위치를 초기화하여 0으로 설정합니다.

 

• 아래쪽 공기청정기(시계 방향 회전)

• 아래쪽 공기청정기 역시 공기를 아래로 밀고, 왼쪽, 위쪽, 오른쪽으로 순차적으로 이동시킵니다.

• 공기청정기 위치도 0으로 초기화합니다.

static void operateCleaner() {
    // 위쪽 공기청정기 (반시계 방향)
    for (int i = airCleanerTop - 1; i > 0; i--) arr[i][0] = arr[i - 1][0];
    for (int i = 0; i < c - 1; i++) arr[0][i] = arr[0][i + 1];
    for (int i = 0; i < airCleanerTop; i++) arr[i][c - 1] = arr[i + 1][c - 1];
    for (int i = c - 1; i > 1; i--) arr[airCleanerTop][i] = arr[airCleanerTop][i - 1];
    arr[airCleanerTop][1] = 0;

    // 아래쪽 공기청정기 (시계 방향)
    for (int i = airCleanerBottom + 1; i < r - 1; i++) arr[i][0] = arr[i + 1][0];
    for (int i = 0; i < c - 1; i++) arr[r - 1][i] = arr[r - 1][i + 1];
    for (int i = r - 1; i > airCleanerBottom; i--) arr[i][c - 1] = arr[i - 1][c - 1];
    for (int i = c - 1; i > 1; i--) arr[airCleanerBottom][i] = arr[airCleanerBottom][i - 1];
    arr[airCleanerBottom][1] = 0;
}

4. getTotalDust() 메소드

• 미세먼지 총합 계산:

• arr 배열을 순회하며 미세먼지(> 0)를 모두 더해 총합을 계산합니다.

 

예시 실행 흐름

1. 입력으로 방의 크기와 미세먼지 초기 상태가 주어집니다.

2. t초 동안 미세먼지 확산과 공기청정기 작동을 반복합니다.

3. 마지막으로 미세먼지가 남아있는 양을 출력합니다.

static int getTotalDust() {
    int sum = 0;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (arr[i][j] > 0) sum += arr[i][j];
        }
    }
    return sum;
}

 

시간 복잡도

• 각 spreadDust와 operateCleaner는 방 크기(r * c)에 대해 한 번씩 처리되므로, 각 반복의 시간 복잡도는 O(r * c)입니다.

• 주어진 시간 t에 대해 t번 반복하므로, 전체 시간 복잡도는 O(t * r * c)가 됩니다.

전체 코드

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

class Main {
    static int r, c, t;
    static int[][] arr, temp;
    static int airCleanerTop, airCleanerBottom;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 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());

        arr = new int[r][c];

        boolean found = false;
        for (int i = 0; i < r; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < c; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                if (arr[i][j] == -1 && !found) {
                    airCleanerTop = i;
                    airCleanerBottom = i + 1;
                    found = true;
                }
            }
        }

        while (t-- > 0) {
            spreadDust();
            operateCleaner();
        }

        System.out.println(getTotalDust());
    }

    static void spreadDust() {
        temp = new int[r][c];
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (arr[i][j] > 0) {
                    int spreadAmount = arr[i][j] / 5;
                    int spreadCount = 0;

                    for (int dir = 0; dir < 4; dir++) {
                        int nx = i + dx[dir];
                        int ny = j + dy[dir];

                        if (nx >= 0 && ny >= 0 && nx < r && ny < c && arr[nx][ny] != -1) {
                            temp[nx][ny] += spreadAmount;
                            spreadCount++;
                        }
                    }
                    temp[i][j] += arr[i][j] - (spreadAmount * spreadCount);
                }
            }
        }
        temp[airCleanerTop][0] = temp[airCleanerBottom][0] = -1;
        arr = temp;
    }

    static void operateCleaner() {
        // 위쪽 공기청정기 (반시계 방향)
        for (int i = airCleanerTop - 1; i > 0; i--) arr[i][0] = arr[i - 1][0];
        for (int i = 0; i < c - 1; i++) arr[0][i] = arr[0][i + 1];
        for (int i = 0; i < airCleanerTop; i++) arr[i][c - 1] = arr[i + 1][c - 1];
        for (int i = c - 1; i > 1; i--) arr[airCleanerTop][i] = arr[airCleanerTop][i - 1];
        arr[airCleanerTop][1] = 0;

        // 아래쪽 공기청정기 (시계 방향)
        for (int i = airCleanerBottom + 1; i < r - 1; i++) arr[i][0] = arr[i + 1][0];
        for (int i = 0; i < c - 1; i++) arr[r - 1][i] = arr[r - 1][i + 1];
        for (int i = r - 1; i > airCleanerBottom; i--) arr[i][c - 1] = arr[i - 1][c - 1];
        for (int i = c - 1; i > 1; i--) arr[airCleanerBottom][i] = arr[airCleanerBottom][i - 1];
        arr[airCleanerBottom][1] = 0;
    }

    static int getTotalDust() {
        int sum = 0;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (arr[i][j] > 0) sum += arr[i][j];
            }
        }
        return sum;
    }
}

 

 

'코딩테스트 > 백준' 카테고리의 다른 글

[Gold V][JAVA] 12865번: 평범한 배낭  (0) 2025.03.13
[Gold V][JAVA] 16928번: 뱀과 사다리 게임  (0) 2025.03.12
[Silver IV][JAVA] 2217번:로프  (1) 2025.03.11
[Silver V][JAVA] 1417번:국회의원선거  (1) 2025.02.17
[Gold II][JAVA] 1202번:보석 도둑  (0) 2025.02.16

티스토리툴바