[BOJ] 17144. 미세먼지 안녕!

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

17144번: 미세먼지 안녕!

처음에 큐를 사용하지 않고 벡터로 구현을 했어서 헤맸던 문제였다...

공기청정기 바람 나오는 거 구현할 때에도 범위 때문에 계속 헷갈렸었다

공기청정기는 위쪽과 아래쪽을 나눠서 각각 구현해줬다. 그냥 문제에서 시키는 대로 한 칸씩 이동시켜주면 된다.

 

미세먼지 확산의 경우에는 확산되는 먼지는 따로 저장해서 나중에 한번에 더해줘야 한다.

바로 더해주면 확산된 곳에서 같은 시간에 다시 확산될 수 도 있기 때문이다

이 부분이랑 공기청정기에서 바람 나와서 이동할 때 범위만 조심해주면 될 것 같다!

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
 
int R, C, T;
int map[50][50];
int sum[50][50];
int air[2];
 
int dx[] = { 0,-1,0,1 };
int dy[] = { 1,0,-1,0 };
 
void goUpair() {
    int x, y;
    x = air[0] - 1;
    y = 0;
 
    if (x < 0) return;
 
    while (x > 0) {
        map[x][y] = map[x - 1][y];
        x--;
    }
    while (y < C - 1) {
        map[x][y] = map[x][y + 1];
        y++;
    }
    while (x < air[0]) {
        map[x][y] = map[x + 1][y];
        x++;
    }
    while (y > 1) {
        map[x][y] = map[x][y - 1];
        y--;
    }
    map[x][1] = 0;
 
}
 
void goDownair() {
    int x, y;
    x = air[1] + 1;
    y = 0;
 
    if (x >= R) return;
 
    while (x < R - 1) {
        map[x][y] = map[x + 1][y];
        x++;
    }
    while (y < C - 1) {
        map[x][y] = map[x][y + 1];
        y++;
    }
    while (x > air[1]) {
        map[x][y] = map[x - 1][y];
        x--;
    }
    while (y > 1) {
        map[x][y] = map[x][y - 1];
        y--;
    }
    map[x][1] = 0;
}
 
void spread() {
    queue<pair<int, int>> q;
 
    //먼지가 있는 곳을 모두 큐에 넣어준다.
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (map[i][j] > 0) {
                q.push(make_pair(i, j));
            }
        }
    }
 
 
    int x, y;
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        int amt = map[x][y] / 5;
 
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
            if (map[nx][ny] == -1) continue;
 
            //확산될때 원래자리에서는 빼주고
            //확산될 자리에서는 더해준다.
            map[x][y] -= amt;
            sum[nx][ny] += amt;
        }
    }
 
    //확산된 먼지들을 더해준다.
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            map[i][j] += sum[i][j];
        }
    }
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> R >> C >> T;
 
    bool flag = true;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> map[i][j];
            if (map[i][j] == -1) {
                if (flag) {
                    //첫번째 공기청정기
                    air[0] = i;
                    flag = false;
                }
                else {
                    //두번째 공기청정기
                    air[1] = i;
                }
            }
        }
    }
 
 
    //T초 동안 확산과 공기청정(위쪽, 아래쪽)을 반복
    for (int i = 0; i < T; i++) {
        memset(sum, 0, sizeof(sum));
        spread();
        goUpair();
        goDownair();
    }
 
 
    //남아있는 먼지 수를 계산
    int ans = 0;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            ans += map[i][j];
        }
    }
 
 
    //공기청정기 2개때문에 빠진 값을 다시 더해준다.
    cout << ans + 2 << '\n';
 
    return 0;
}