17144 : 미세먼지 안녕

formula

Grid 밀기

Implementation

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int R, C, T;
int matrix[50][50];
bool cleaner_find = false;
int cleaner_top = 0;
int cleaner_bot = 0;

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


void propagation() {
    int temp[50][50] = { 0, };

    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            if (matrix[r][c] > 0) {
                int amount = matrix[r][c]; // 현재 양
                int cnt = 0; // 확산 방향 수

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

                    if (nx >= 0 && ny >= 0 && nx < R && ny < C && matrix[nx][ny] != -1) {
                        temp[nx][ny] += amount / 5; //전파 값만 계산
                        cnt++; // 방향 전파 추가
                    }
                }
                matrix[r][c] -= cnt * (amount/5); // 원본 변경
            }
        }
    }

    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            matrix[r][c] += temp[r][c]; // 전파 값 취합
        }
    }
}

// CCW
void upper_clean() {
    // 아래 shift(맨 좌측)
    for (int i = cleaner_top - 1; i > 0; i--) {
        matrix[i][0] = matrix[i - 1][0];
    }

    // 왼쪽 shift(맨 윗줄)
    for (int i = 0; i < C-1; i++) {
        matrix[0][i] = matrix[0][i + 1];
    }

    // 위로 shift(맨 우측)
    for (int i = 0; i < cleaner_top; i++) {
        matrix[i][C - 1] = matrix[i + 1][C - 1];
    }

    // 우측 shift(공기 청정기 라인)
    for (int i = C - 1; i > 1; i--) {
        matrix[cleaner_top][i] = matrix[cleaner_top][i - 1];
    }

    matrix[cleaner_top][1] = 0; // 공기청정기 나가는 바람
}

// CW
void lower_clean() {
    // 위쪽 shift(맨 좌측)
    for (int i = cleaner_bot + 1; i < R - 1; i++) {
        matrix[i][0] = matrix[i + 1][0];
    }

    // 왼쪽 shift(맨 아랫줄)
    for (int i = 0; i < C - 1; i++) {
        matrix[R - 1][i] = matrix[R - 1][i + 1];
    }

    // 아래 shift(맨 오른쪽)
    for (int i = R - 1; i > cleaner_bot; i--) {
        matrix[i][C - 1] = matrix[i - 1][C - 1];
    }

    // 우측 shift(공기청정기 라인)
    for (int i = C - 1; i > 1; i--) {
        matrix[cleaner_bot][i] = matrix[cleaner_bot][i - 1];
    }

    matrix[cleaner_bot][1] = 0;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> R >> C >> T; // row, col, T초 지난후 미세먼지 양

    //input
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> matrix[i][j];

            // 공기청정기 위치 fix
            if (matrix[i][j] == -1) {
                if (!cleaner_find) {
                    cleaner_top = i;
                    cleaner_bot = i + 1;
                    cleaner_find = true;
                }
            }
        }
    }

    int res = 0;

    while (T > 0) {
        T--;

        propagation();
        upper_clean();
        lower_clean();
    }

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (matrix[i][j] == -1) continue;
            res += matrix[i][j];
        }
    }

    cout << res;

}