(C++) 백준 17144 미세먼지 안녕!

문제 및 풀이

https://www.acmicpc.net/problem/17144

ㅋㅋㅋ 항상 느끼는거지만 맨날 새로 공부 안하니까 비슷하게만 푼다 ㅠ ㅎㅎㅎㅋㅋㅋ 비슷한유형 몇번 풀었는데 항상 큐로 풀어서 이문제도 큐로 풀었다 (승등히 고생함)

큐 사용하지 말고..이런 배열 로테이션 문제 배열 복사해서 옮기면 된다. 이문제는 특히 공기청정기에 들어간 값은 0으로 처리하면 되니까.. 공기청정기 바로 직전 위치부터 카피해오면 된다.

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const pair<int,int> dir[4] = {{-1,0}, {1,0}, {0,1}, {0,-1}};

int R,C,T;
int total, ans;
int top_row, bottom_row;

int arr[55][55];
int tmp[55][55];


void diffusion() {

    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
            tmp[i][j] = 0;

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {

            int now = arr[i][j];
            if (now == 0 || now == -1) continue;

            int cnt = 0;
            for (int k = 0; k < 4; k++) {
                int yy = i + dir[k].first;
                int xx = j + dir[k].second;
                if (yy < 0 || xx < 0 || yy >= R || xx >= C) continue;
                if (arr[yy][xx] == -1) continue;
                cnt++;
                tmp[yy][xx] += now / 5;
            }

            tmp[i][j] -= (now / 5) * cnt;
        }
    }

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

}


void move(){

    total -= arr[top_row-1][0];
    total -= arr[bottom_row+1][0];

    // upside move
    for(int i=top_row-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=1; i<=top_row; i++){
        arr[i-1][C-1] = arr[i][C-1];
    }

    for(int j=C-1; j>1; j--){
        arr[top_row][j] = arr[top_row][j-1];
    }


    // downside move

    for(int i=bottom_row+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>=bottom_row; i--){
        arr[i][C-1] = arr[i-1][C-1];
    }

    for(int j=C-1; j>1; j--){
        arr[bottom_row][j] = arr[bottom_row][j-1];
    }

    arr[top_row][1]=0;
    arr[bottom_row][1]=0;

}




int main(){

    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin>>R>>C>>T;
    bool isfirst=true;

    for(int i=0; i<R; i++){
        for(int j=0; j<C;j ++){
            cin>>arr[i][j];
            if(arr[i][j]==-1){
                if(isfirst) {
                    isfirst=false;
                    top_row=i;
                }
                else bottom_row = i;
            }
            else
                total+=arr[i][j];
        }
    }

    while(T--){
        diffusion();
        move();
    }

    cout<<total;
}