[삼성SW테스트] 백준 17144번 - 미세먼지 안녕!

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

17144번: 미세먼지 안녕!

재미있는 시뮬레이션 문제였다.

 

유의할 점은

1. 미세먼지들이 동시에 확산되므로 칸 마다 더해야 할 사방의 요소들을 3차원 벡터에 저장하고 각 칸에서 남아있는 먼지에 해당 칸의 더해줘야할 요소들을 모두 더해줘야 한다는 것,

2. 청소기에서 처음에 나오는 칸은 먼지의 양을 0으로 해줘야 하는 처리가 필요한 점 

정도였다.

 

처음에 구상한대로 답이 나오지 않아 무엇이 문제인가 하고 1~2분 코드를 다시 보니 벡터 초기화를 까먹어 틀린답을 내놨다. 연산에 필요한 벡터는 해당 연산 후 clear()를 제대로 해주는걸 잊지말자! 한번에 성공떠서 기분 좋음 :)

 

#include <iostream>
#include <vector>
#define maxlen 51
 
using namespace std;
 
int R, C, T;
int Map[maxlen][maxlen];
vector<int> Plus[maxlen][maxlen]; // 얼마나 더해야 하는건지
int temp[maxlen][maxlen];
 
typedef struct dir{
    int dr, dc;
}dir;
dir direction[4] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } }; //  E W S N
int Robot_Up_R, Robot_Down_R;
int Robot_C = 1;
bool Up_Exist = false;
 
void Copy2Temp(){
    for (int r = 1; r <= R; r++){
        for (int c = 1; c <= C; c++){
            temp[r][c] = Map[r][c];
        }
    }
}
 
void Spread(){
    // 미세먼지 확산
    for (int r = 1; r <= R; r++){
        for (int c = 1; c <= C; c++){
            if (Map[r][c] != -1 && Map[r][c] != 0){
                // 먼지 있다면 퍼지자
                int spread_cnt = 0;
                for (int i = 0; i<4; i++){
                    int n_r = r + direction[i].dr;
                    int n_c = c + direction[i].dc;
                    if (n_r >= 1 && n_r <= R && n_c >= 1 && n_c <= C){
                        if (Map[n_r][n_c] != -1){
                            spread_cnt++;
                            Plus[n_r][n_c].push_back(Map[r][c] / 5);
                        }
                    }
                }
                Map[r][c] -= (Map[r][c]/5) * spread_cnt;
            }
        }
    }
 
    for (int r = 1; r <= R; r++){
        for (int c = 1; c <= C; c++){
            for (int plus = 0; plus < Plus[r][c].size(); plus++){
                Map[r][c] += Plus[r][c][plus];
            }
            Plus[r][c].clear();
        }
    }
}
 
void Circulation(){
    // 공기 청정기 가동
    Copy2Temp();
 
    // 위쪽 부분부터
    // Map과 temp를 활용
    Map[Robot_Up_R][Robot_C + 1] = 0;
    for (int new_c = 3; new_c <= C; new_c++){
        Map[Robot_Up_R][new_c] = temp[Robot_Up_R][new_c - 1];
    }
    for (int new_r = Robot_Up_R - 1; new_r >= 1; new_r--){
        Map[new_r][C] = temp[new_r + 1][C];
    }
    for (int new_c = C - 1; new_c >= 1; new_c--){
        Map[1][new_c] = temp[1][new_c + 1];
    }
    for (int new_r = 2; new_r < Robot_Up_R; new_r++){
        Map[new_r][1] = temp[new_r - 1][1];
    }
 
    // 아랫쪽 부분 순환
    Map[Robot_Down_R][Robot_C + 1] = 0;
    for (int new_c = 3; new_c <= C; new_c++){
        Map[Robot_Down_R][new_c] = temp[Robot_Down_R][new_c - 1];
    }
    for (int new_r = Robot_Down_R + 1; new_r <= R; new_r++){
        Map[new_r][C] = temp[new_r - 1][C];
    }
    for (int new_c = C - 1; new_c >= 1; new_c--){
        Map[R][new_c] = temp[R][new_c + 1];
    }
    for (int new_r = R - 1; new_r > Robot_Down_R; new_r--){
        Map[new_r][1] = temp[new_r + 1][1];
    }
}
 
int DustAnswer(){
    int dust = 0;
    for (int r = 1; r <= R; r++){
        for (int c = 1; c <= C; c++){
            if (Map[r][c] != -1)
                dust += Map[r][c];
        }
    }
    return dust;
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> R >> C >> T;
    for (int r = 1; r <= R; r++){
        for (int c = 1; c <= C; c++){
            cin >> Map[r][c]; // 0 : 청정구역, -1: 로봇, 기타숫자: 미세먼지 양.
            if (Map[r][c] == -1 && !Up_Exist){
                Up_Exist = true;
                Robot_Up_R = r;
            }
            else if (Map[r][c] == -1 && Up_Exist){
                Robot_Down_R = r;
            }
        }
    }
    int time = 0;
    while (time < T){
        time++;
        Spread();
        Circulation();
    }
    cout << DustAnswer() << '\n';
    return 0;
}