미세먼지 안녕!(백준 17144번)

문제

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

17144번: 미세먼지 안녕!

알고리즘 풀이

1. 미세먼지를 분산시킬때는 동시에 일어나는 것이기 때문에 배열에 하나하나 접근해서 바꾸다 보면 분산시켜서 더해준 구역을 

분산시켜서 동시에 한다는 조건을 만족하지 못한다. 그렇기 때문에 임시로 저장해놓을 배열을 하나 만들어서 분산시키는 것과 분산시킨 구역의 남은 미세먼지 값을 임시 배열에 저장한다.

2. 임시 배열의 값들을 진짜 배열에 복사해준다.

3. 공기청정기는 공기가 지나는 길을 벡터에 저장하고 벡터의 값들을 인덱스 하나씩 앞당긴다. 그리고 제일 마지막 인덱스를 공기청정기 바로 앞이기 떄문에 0으로 해준다.

4. -1를 제외하고 합을 구해준다.

 

후기

그냥 구현하는 문제였는데 시간을 상당히 오래썼다. 그 이유는 중간중간 잦은 실수가 너무 많았다. 미리 설계를 하고 들어갔으면 실수를 더 줄일 수 있을 것 같다. 어렵지는 않은 문제였는데 너무 시간을 많이 투자해서 아쉬웠다.

 

코드

 

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
int R,C,T;
int map[55][55],temp[55][55];
int DX[4] = {0,0,1,-1};
int DY[4] = {1,-1,0,0};
vector<pair<int,int>> v;
void map_print(void){
    for(int i = 0;i<R;i++){
        for(int j = 0;j<C;j++){
            cout << map[i][j] << "  ";
        }
        cout << "\n";
    }
    cout << "\n";
}
int map_sum(void){
    int result = 0;
    for(int i = 0;i<R;i++){
        for(int j = 0;j<C;j++){
            result+=map[i][j];
        }
    }
    return result+2;
}
void map_cpy(void){
    for(int i = 0;i<R;i++){
        for(int j = 0;j<C;j++){
            map[i][j] = temp[i][j];
        }
    }
}
void temp_cp(void){
    for(int i = 0;i<R;i++){
        for(int j = 0;j<C;j++){
            temp[i][j] = map[i][j];
        }
    }
}    
void diffusion(void){
    for(int i = 0;i<R;i++){
        for(int j = 0;j<C;j++){
            int cnt = 0;
            if(map[i][j] != -1 && map[i][j] != 0){
                for(int k = 0;k<4;k++){
                    if(i+DY[k]<0||j+DX[k]<0||i+DY[k]>=R || j+DX[k]>=C)
                    {continue;}
                    else if(map[i+DY[k]][j+DX[k]] == -1){continue;}
                    else{
                        temp[i+DY[k]][j+DX[k]] = temp[i+DY[k]][j+DX[k]]+map[i][j]/5;
                        cnt++;
                    }
                }
            }
            temp[i][j] = temp[i][j]-((map[i][j]/5)*cnt);
        }
    }
    map_cpy();
}
void wind(void){
    int ar;
    vector<pair<int, int>> pts;
 
    //상
    ar = v[0].first;
    for (int r = ar - 1; r >= 0; r--) {
        pts.push_back(make_pair(r, 0));
    }
    for (int c = 0; c < C; c++) {
        pts.push_back(make_pair(0, c));
    }
    for (int r = 0; r <= ar; r++) {
        pts.push_back(make_pair(r, C - 1));
    }
    for (int c = C - 1; c > 0; c--) {
        pts.push_back(make_pair(ar, c));
    }
 
    for (int i = 0; i < pts.size() - 1; i++) {
        map[pts[i].first][pts[i].second] = map[pts[i + 1].first][pts[i + 1].second];
    }
    map[pts[pts.size() - 1].first][pts[pts.size() - 1].second] = 0;
    pts.clear();
 
    //하
    ar = v[1].first;
    for (int r = ar + 1; r < R; r++) {
        pts.push_back(make_pair(r, 0));
    }
    for (int c = 0; c < C; c++) {
        pts.push_back(make_pair(R - 1, c));
    }
    for (int r = R - 1; r >= ar; r--) {
        pts.push_back(make_pair(r, C - 1));
    }
    for (int c = C - 1; c >= 1; c--) {
        pts.push_back(make_pair(ar, c));
    }
    for (int i = 0; i < pts.size() - 1; i++) {
        map[pts[i].first][pts[i].second] = map[pts[i + 1].first][pts[i + 1].second];
    }
    map[pts[pts.size() - 1].first][pts[pts.size() - 1].second] = 0;
}
int main(int argc, char* argv[]){
    cin >> R >> C >> T;
    for(int i = 0;i<R;i++){
        for(int j = 0;j<C;j++){
            cin >> map[i][j];
            temp[i][j] = map[i][j];
            if(map[i][j] == -1){
                v.push_back(make_pair(i,j));
            }
        }
    }
    for(int i = 0;i<T;i++){
        diffusion();
        temp_cp();
        wind();
        temp_cp();
    }
    cout << map_sum();
}