백준 17144번 - 미세먼지 안녕!

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

1초 동안의 진행상황을 문제에 제시된 그대로 구현해주면 된다.

1)미세먼지의 확산 작업

2)공기 청정기 이동 과정

미세먼지가 확산 될 때

기존 미세먼지의 정보를 하나 더 만들고, 확산이 될 때 확산되는 양만큼 더해주면 된다.

만약 미세먼지의 정보를 하나 더 만들지 않으면, 다른 칸에서 확산된 미세먼지의 양이 확산되어 올바른 양만큼 확산되지 않기 때문이다.

다음으로 공기 청정기의 이동 과정은 함수를 하나 더 만든 뒤에

방향 설정만 다르게 해주는 식으로 동작하도록 했다. 같은 소스를 2번이나 쓸 필요가 없기 때문이다.

바람의 이동 과정은 다음과 같다.

1) x축 +1, y축 -1, x축 -1, y축 +1  

2)x축 +1, y축 +1, x축 -1, y축 -1

y축만 진행 과정을 변경 해주면 올바른 답을 구할 수 있다.

#include <iostream>
#include <vector>
using namespace std;
 
vector<vector<int>> map;
vector<pair<int, int>> clean; //청정기
vector<pair<int, int>> mm;//미세먼지
 
int dy[4] = {0,-1,0,1 };
int dx[4] = { 1,0,-1,0};
int R, C, T;
 
void func(int y, int x) {
    
    vector<vector<int>> copy_map = map;
    
    for (int dir = 0; dir < 4;) {
        
        int ny = y + dy[dir];
        int nx = x + dx[dir];
        
        if (ny < 0 || ny >= R || nx < 0 || nx >= C) {
            dir++;
            continue;
        }
        
        //공기 청정기 자리(끝 지점)
        if (map[ny][nx] == -1)
            return;
        
        //공기 청정기 자리(시작 지점)
        if (map[y][x] == -1) {
            map[ny][nx] = 0;
        }
        else {
            map[ny][nx] = copy_map[y][x];
        }
        
        y = ny;
        x = nx;
    }
}
int main() {
    
    std::ios_base::sync_with_stdio(false);
    cin >> R >> C >> T;
    
    map= vector<vector<int>> (R, vector<int>(C, 0));
    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            cin >> map[r][c];
            if (map[r][c] == -1)
                clean.push_back(make_pair(r, c));
            else if (map[r][c] > 0)
                mm.push_back(make_pair(r, c));
        }
    }
    
    for (int t = 0; t < T; t++) {
        
        vector<pair<int, int>> copy_mm;
        vector<vector<int>> copy_map=map;
        
        
        for (int i = 0; i < mm.size(); i++) {
            int y = mm[i].first;
            int x = mm[i].second;
            
            int mm_size = copy_map[y][x] / 5;
            int cnt = 0;
            for (int dir = 0; dir < 4; dir++) {
                int ny = y + dy[dir];
                int nx = x + dx[dir];
                
                if (ny < 0 || ny >= R || nx < 0 || nx >= C)
                    continue;
                
                if (map[ny][nx] == -1)
                    continue;
                
                cnt += mm_size;
                map[ny][nx] += mm_size;
                
            }
            map[y][x] -= cnt;
        }
        
        dy[1] = -1, dy[3] = 1;
        func(clean[0].first, clean[0].second);
        
        
        dy[1] = 1, dy[3] = -1;
        func(clean[1].first, clean[1].second);
        
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                if (map[r][c] > 0) {
                    copy_mm.push_back(make_pair(r, c));
                }
            }
        }
        
        mm = copy_mm;
    }
    
    int ans = 0;
    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            
            if (map[r][c] > 0) {
                ans += map[r][c];
            }
        }
    }
    
    cout << ans << endl;
    
    return 0;
}