[BOJ] 17144 : 미세먼지 안녕

17144 : 미세먼지 안녕

풀이

2019 상반기 삼성전자DS 오전 시험 1번 변형문제.

시뮬레이션

그냥 T초동안 0보다 큰값 큐에 넣고, 4방향 확산해준다음에

공기청정기(위,아래 부분 배열돌리기) 해주면 된다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstring>
#include <queue>
using namespace std;
int arr[50][50];
vector<pair<int, int>> aircon;
const int dx[] = { 0,1,0,-1 };
const int dy[] = { -1,0,1,0 };

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

    //미세먼지 안녕
    int r, c, t;
    cin >> r >> c >> t;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == -1) {
                aircon.push_back({i,j});
            }
        }
    }
    while (t--) {
        //미세먼지 확산
        //(x,y),value
        queue<pair<pair<int, int>, int>> q;
        //큐에 먼지를 넣는다.
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (arr[i][j]>0) {
                    q.push({ {i,j},arr[i][j] });
                }
            }
        }
        //먼지확산
        while (!q.empty()) {
            int x = q.front().first.first;
            int y = q.front().first.second;
            int num = q.front().second;
            q.pop();
            int cnt = 0;
            for (int dir = 0; dir < 4; dir++) {
                int nx = x + dx[dir];
                int ny = y + dy[dir];
                if (nx >= 0 && nx < r&&ny >= 0 && ny < c && arr[nx][ny] != -1) {
                    arr[nx][ny] += num / 5;
                    cnt++;
                }
            }
            arr[x][y] -= num / 5 * cnt;
        }

        // 위로 청정기 가동
        int x = aircon[0].first;
        int y = aircon[0].second;
        x--;
        while (x > 0) {
            arr[x][y] = arr[x - 1][y];
            x--;
        }
        while (y < c - 1) {
            arr[x][y] = arr[x][y + 1];
            y++;
        }
        while (x<aircon[0].first) {
            arr[x][y] = arr[x + 1][y];
            x++;
        }
        while (y > 1) {
            arr[x][y] = arr[x][y - 1];
            y--;
        }
        arr[x][y] = 0;

        //아래로 청정기 가동
        x = aircon[1].first;
        y = aircon[1].second;
        x++;
        while (x < r-1) {
            arr[x][y] = arr[x + 1][y];
            x++;
        }
        while (y < c - 1) {
            arr[x][y] = arr[x][y + 1];
            y++;
        }
        while (x>aircon[1].first) {
            arr[x][y] = arr[x - 1][y];
            x--;
        }
        while (y > 1) {
            arr[x][y] = arr[x][y - 1];
            y--;
        }
        arr[x][y] = 0;
    }
    //남은 미세먼지 계산
    int sum = 0;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (arr[i][j]>0) {
                sum += arr[i][j];
            }
        }
    }
    cout << sum;
    return 0;
}
Written on April 20, 2019