[백준 17144] 미세먼지 안녕!

[백준 17144] 미세먼지 안녕!

문제 링크

#include "header.h"
using namespace std;
//1.5h

int r, c, T;
int room[51][51];
int temp_room[51][51];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
queue<pair<int, int>> dust;
vector<pair<int, int>> robot;
void input()
{
    cin >> r >> c >> T;
    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            cin >> room[i][j];
            if (room[i][j]){
                if (room[i][j] == -1) robot.push_back({i, j});
                else dust.push({i, j});
            }
        }
    }
}
void spreadDust()
{
    memset(temp_room, 0, sizeof(temp_room));

    while (!dust.empty())
    {
        int top_x = dust.front().first;
        int top_y = dust.front().second;
        dust.pop();

        int cnt_spread = 0;
        int spread_amount = room[top_x][top_y] / 5;
        for (int i = 0; i < 4; i++)
        {
            int nx = top_x + dx[i];
            int ny = top_y + dy[i];

            if (room[nx][ny] == -1 || nx < 0 || ny < 0 || nx >= r || ny >= c)
                continue;
            cnt_spread++;
            temp_room[nx][ny] += spread_amount;
        }
        temp_room[top_x][top_y] += room[top_x][top_y] - (spread_amount * cnt_spread);
    }

    memcpy(room, temp_room, sizeof(room));
}
void cleanDust()
{
    pair<int, int> upperWind = robot[0];
    pair<int, int> underWind = robot[1];
    memset(temp_room, 0, sizeof(temp_room));

    //upper
    int x = upperWind.first;
    int y = upperWind.second;

    for (int i = x - 1; i > 0; i--) temp_room[i][0] = room[i - 1][0];
    for (int i = 0; i < c - 1; i++) temp_room[0][i] = room[0][i + 1];
    for (int i = 1; i <= x; i++) temp_room[i - 1][c - 1] = room[i][c - 1];
    for (int i = c - 1; i > 1; i--) temp_room[x][i] = room[x][i - 1];

    //under
    x = underWind.first;
    y = underWind.second;

    for (int i = x + 1; i < r - 1; i++) temp_room[i][0] = room[i + 1][0];
    for (int i = 0; i < c - 1; i++) temp_room[r - 1][i] = room[r - 1][i + 1];
    for (int i = r - 1; i >= x; i--) temp_room[i][c - 1] = room[i - 1][c - 1];
    for (int i = c - 1; i > 1; i--) temp_room[x][i] = room[x][i - 1];


    //공기청정기의 바람이 닿지 않는 곳
    for(int i=1; i<upperWind.first; i++){
        for(int j=1; j<c-1; j++){
            temp_room[i][j] = room[i][j];
        }
    }

    for(int i=underWind.first+1; i<r-1; i++){
        for(int j=1; j<c-1; j++){
            temp_room[i][j] = room[i][j];
        }
    }

    memcpy(room, temp_room, sizeof(temp_room));

}

int addDust()
{
    int ret = 0;

    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            if(room[i][j]<=0) continue;
            ret += room[i][j];
        }
    }

    return ret;
}
void pushDust(){
    while (!dust.empty()) dust.pop();
    
    for(int i=0; i<r; i++){
        for(int j=0; j<c; j++){
            if(room[i][j] >= 0) dust.push({i, j});
        }
    }
}
void solve()
{
    for (int i = 0; i < T; i++)
    {
        spreadDust();
        cleanDust();
        pushDust();
    }

    cout << addDust() << endl;
}
int main()
{
    input();
    solve();

    return 0;
}

• 간단한 구현문제. bfs로 풀었다.
• 공기 청정기를 돌릴 때 하드코딩으로 풀었는데, 시계방향과 반시계방향을 고려해서 푸는 방법도 있는 듯.