백준 17144번 [미세먼지 안녕!](C++)-yes6686- 티스토리

백준 문제 풀이: 17144 [미세먼지 안녕!]

---

문제 링크: https://www.acmicpc.net/problem/17144

문제 설명:

격자 형태의 방에서 공기청정기가 작동하여 미세먼지를 확산 및 제거하는 과정을 시뮬레이션하는 문제입니다. 주어진 시간 동안 미세먼지가 방 전체에 확산한 후 공기청정기를 작동시켜 최종적으로 남아있는 미세먼지의 양을 계산합니다.

입력:

• 첫째 줄에 방의 크기 R과 C (1 ≤ R, C ≤ 50) 및 시간 T (1 ≤ T ≤ 1000)가 주어집니다.
• 이후 R개의 줄에 방 상태가 주어집니다.
• 0은 빈 칸, -1은 공기청정기 위치, 양수는 해당 칸의 미세먼지 농도를 의미합니다.

출력:

• 시간 T가 지난 후 방에 남아있는 미세먼지의 총 양을 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <cstring>
using namespace std;

int R, C, T;
int arr[51][51];
int temp[51][51];
int air_cleaner[2];

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

void spread_dust() {
    memset(temp, 0, sizeof(temp));
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (arr[i][j] > 0) {
                int spread_amount = arr[i][j] / 5;
                int spread_count = 0;
                for (int k = 0; k < 4; k++) {
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    if (nx >= 0 && ny >= 0 && nx < R && ny < C && arr[nx][ny] != -1) {
                        temp[nx][ny] += spread_amount;
                        spread_count++;
                    }
                }
                arr[i][j] -= spread_amount * spread_count;
            }
        }
    }
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            arr[i][j] += temp[i][j];
        }
    }
}

void clean_air() {
    // Upper part
    for (int i = air_cleaner[0] - 1; i > 0; i--) arr[i][0] = arr[i - 1][0];
    for (int j = 0; j < C - 1; j++) arr[0][j] = arr[0][j + 1];
    for (int i = 0; i < air_cleaner[0]; i++) arr[i][C - 1] = arr[i + 1][C - 1];
    for (int j = C - 1; j > 1; j--) arr[air_cleaner[0]][j] = arr[air_cleaner[0]][j - 1];
    arr[air_cleaner[0]][1] = 0;

    // Lower part
    for (int i = air_cleaner[1] + 1; i < R - 1; i++) arr[i][0] = arr[i + 1][0];
    for (int j = 0; j < C - 1; j++) arr[R - 1][j] = arr[R - 1][j + 1];
    for (int i = R - 1; i > air_cleaner[1]; i--) arr[i][C - 1] = arr[i - 1][C - 1];
    for (int j = C - 1; j > 1; j--) arr[air_cleaner[1]][j] = arr[air_cleaner[1]][j - 1];
    arr[air_cleaner[1]][1] = 0;
}

int main() {
    cin >> R >> C >> T;
    int air_idx = 0;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == -1) {
                air_cleaner[air_idx++] = i;
            }
        }
    }

    while (T--) {
        spread_dust();
        clean_air();
    }

    int total_dust = 0;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (arr[i][j] > 0) total_dust += arr[i][j];
        }
    }

    cout << total_dust << '\n';
    return 0;
}

예제

입력:
7 8 1
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0

출력:
188

---

코드 설명

• 미세먼지 확산: 각 칸에서 4방향으로 확산하며, 확산량은 5로 나눈 몫입니다. 벽(-1)으로는 확산되지 않습니다.
• 공기청정기 작동: 공기청정기가 위치한 행을 기준으로 공기를 시계 방향과 반시계 방향으로 이동시킵니다.
• 총 미세먼지 계산: 시뮬레이션이 끝난 후 배열에 남아 있는 미세먼지를 모두 더합니다.

시간 복잡도

• 미세먼지 확산과 공기청정기 작동 과정에서 최대 O(R × C × T)의 연산이 발생합니다.

---

결과

코드는 T초 후 남은 미세먼지 양을 정확히 계산하며, 문제의 요구 사항을 충족합니다. 더 효율적인 구현이나 추가 최적화가 가능하다면 논의 부탁드립니다!