[백준][BOJ][C++][17144번] 미세먼지 안녕!

이 문제는 아래의 조건을 코드로 잘 짜는 것이 중요했습니다. 처음 코드를 짤때 확산되는 미세먼지를 모두 q에 넣고 구현하였더니 시간초과로 정답을 맞추지 못하여 배열을 하나 더만들어 확산되는 미세먼지를 따로 저장해 놓는 방식으로 구현하였습니다.

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

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

코드

#include<iostream>
#include<queue>
#include<memory.h>
using namespace std;
struct{
    int x;
    int y;
}cl[2];
 
struct q_v {
    int x;
    int y;
    int value;
};
int ans;
int r, c, t;
int temp_v0[51];
int temp_v1[51];
int room[51][51];
int room_sum[51][51];
int p_x[4] = { 1,-1,0,0 };
int p_y[4] = { 0,0,1,-1 };
queue<q_v> q;
 
void print() {
    for (int y = 1; y <= r; y++) {
        for (int x = 1; x <= c; x++) {
            cout << room[y][x]<<" ";
            }
        cout << endl;
        }
    cout << endl;
}
 
void move_m() {
    int temp1_c0 = 0; int temp2_c0 = 0;
    int temp1_c1 = 0; int temp2_c1 = 0;
 
    for (int a =2; a <= c; a++) {
        temp2_c0 = room[cl[0].y][a];
        temp2_c1 = room[cl[1].y][a];
        room[cl[0].y][a] = temp1_c0; room[cl[1].y][a] = temp1_c1;
        temp1_c0 = temp2_c0; temp1_c1 = temp2_c1;
    }//----> 이방향
 
    for (int a = cl[0].y-1; a > 0;a--) {
        temp2_c0 = room[a][c];
        room[a][c] = temp1_c0;
        temp1_c0 = temp2_c0;
    }// 오른쪽 끝에서 cl0의 움직임
 
    for (int a = cl[1].y+1; a <= r; a++) {
        temp2_c1 = room[a][c];
        room[a][c] = temp1_c1;
        temp1_c1 = temp2_c1;
    }// 오른쪽 끝에서 cl1의 움직임
 
    for (int a = c-1; a > 1;a--) {
        temp2_c0 = room[1][a];
        temp2_c1 = room[r][a];
        room[1][a] = temp1_c0; room[r][a] = temp1_c1;
        temp1_c0 = temp2_c0; temp1_c1 = temp2_c1;
    }// <----- 이방향
 
    for (int a = 1; a < cl[0].y;a++) {
        temp2_c0 = room[a][1];
        room[a][1] = temp1_c0;
        temp1_c0 = temp2_c0;
    }// 왼쪽 끝에서 cl0의 움직임
 
    for (int a = r; a > cl[1].y; a--) {
        temp2_c1 = room[a][1];
        room[a][1] = temp1_c1;
        temp1_c1 = temp2_c1;
    }// 왼쪽 끝에서 cl1의 움직임
 
}
 
void sp() {
    while (t--){ // 입력으로 들어온 t초만큼만 돌려줌
        while (!q.empty()) {
            q_v now_ = q.front();
            q.pop();
            if (now_.value / 5 == 0) continue;
            int summ = now_.value / 5;
            for (int dis = 0; dis < 4; dis++) {
                int nx = now_.x + p_x[dis];
                int ny = now_.y + p_y[dis];
                if (nx > 0 && nx < c + 1 && ny>0 && ny < r + 1 && room[ny][nx] != -1) {
 
                    room_sum[ny][nx] += summ;
                    room[now_.y][now_.x] -= summ;
                }
            } //4방향
        }//while
        for (int y = 1; y <= r; y++) {
            for (int x = 1; x <= c; x++) {
                room[y][x] += room_sum[y][x];
            }
        }
        move_m();//공기청정기가 돌아가는 부분
        for (int y = 1; y <= r; y++) {
            for (int x = 1; x <= c; x++) {
                if (room[y][x] != 0) {
                    q_v n;
                    n.x = x;
                    n.y = y;
                    n.value = room[y][x];
                    q.push(n);
                }
            }
        }
 
        memset(room_sum, 0, sizeof(room_sum));
        
    }
    for (int y = 1; y <= r; y++) {
        for (int x = 1; x <= c; x++) {
            ans += room[y][x];
        }
    }
 
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> r >> c >> t;
    int aa = 0; q_v temp; memset(room_sum, 0, sizeof(room_sum));
    for (int y = 1; y <= r; y++) {
        for (int x = 1; x <= c; x++) {
            cin >> room[y][x];
            if (room[y][x] == -1) {
                cl[aa].x = x;
                cl[aa].y = y;
                aa++;
            } //공기청정기 저장
            if (room[y][x] != -1 && room[y][x] != 0) {
                temp.x = x;
                temp.y = y;
                temp.value = room[y][x];
                q.push(temp);
            }//미세먼지 저장
        }
    }
    sp();
    cout << ans+2;
}