[백준 17144] 미세먼지 안녕! (C++) - 51

문제

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

17144번: 미세먼지 안녕!

생각

확산하는 함수와 청소하는 함수를 2개 만들었다.

확산하는 함수에서 확산을 할 때 map에 있는 값에다가 더할지 아니면 아예 새로 더할지 고민을 했다.

map[cy][cx] = map[cy][cx] - spreadDust * dir;

이 부분에서 연산이 빼기 이기 때문에 최종 값에 영향을 안 준다.

따라서 그대로 map에 연산을 하는 방식을 취했다.

 

원래 map[51][51] 로 설정을 했으나 모든 반례들이 통과를 하지만 백준에 제출을 할 때 0%도 올라가지 않고 틀렸다고 나온다.

그래서 map[1001][1001]로 설정을 하니깐 바로 정답이 나온다.

왜 그런건지는 잘 모르겠다. ㅠㅠ

코드

#include <iostream>
#include <queue>
using namespace std;

int r, c, t;
int map[1001][1001];
int f1, f2;
bool flag = false;
int sol = 0;
int dy[4] = {1, 0, -1 ,0};
int dx[4] = {0, 1, 0, -1};

void spread() {
    queue<pair<pair<int, int>, int>> q;
    for(int i = 0; i < r; i++) {
        for(int j = 0; j < c; j++) {
            if(map[i][j] != -1 && map[i][j] != 0) {
                q.push({{i, j}, map[i][j]});
            }
        }
    }
    while(!q.empty()) {
        auto[cy, cx] = q.front().first;
        int curDust = q.front().second;
        q.pop();
        int dir = 4;

        //4방향 가능한지 체크
        for(int i = 0; i < 4; i++) {
            int ny = cy + dy[i];
            int nx = cx + dx[i];
            if(ny < 0 || nx < 0 || ny >= r || nx >= c) dir--;
            if(map[ny][nx] == -1) dir--;
        }
        int spreadDust = curDust / 5;
        map[cy][cx] = map[cy][cx] - spreadDust * dir;

        //가능한 곳에 미세먼지 확산
        for(int i = 0; i < 4; i++) {
            int ny = cy + dy[i];
            int nx = cx + dx[i];
            if(ny < 0 || nx < 0 || ny >= r || nx >= c) continue;
            if(map[ny][nx] == -1) continue;
            map[ny][nx] = map[ny][nx] + spreadDust;
        }
    }
}

void clean() {
    //왼쪽
    for(int i = f1 - 1; i > 0; i--) map[i][0] = map[i - 1][0];
    //위
    for(int i = 0; i < c - 1; i++) map[0][i] = map[0][i + 1];
    //오른쪽
    for(int i = 0; i < f1; i++) map[i][c - 1] = map[i + 1][c - 1];
    //아래
    for(int i = c - 1; i > 1; i--) map[f1][i] = map[f1][i - 1];
    map[f1][1] = 0;

    //왼
    for(int i = f2 + 1; i < r - 1; i++) map[i][0] = map[i + 1][0];
    //아래
    for(int i = 0; i < c - 1; i++) map[r - 1][i] = map[r - 1][i + 1];
    //오른쪽
    for(int i = r - 1; i > f2; i--) map[i][c - 1] = map[i - 1][c - 1];
    //위
    for(int i = c - 1; i > 1; i--) map[f2][i] = map[f2][i - 1];
    map[f2][1] = 0;

    /*
    cout << "\n";
    for(int i = 0; i < r; i++) {
        for(int j = 0; j < c; j++) {
            cout << map[i][j] << " ";
        }
        cout << "\n";
    }
    */
}

int main() {
    cin >> r >> c >> t;
    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 == false){
                    f1 = i;
                    flag = true;
                }
                else f2 = i;
            }
        }
    }
    for(int i = 1; i <= t; i++) {
        spread();
        clean();
    }
    for(int i = 0; i < r; i++) {
        for(int j = 0; j < c; j++) {
            if(map[i][j] != -1) {
                sol += map[i][j];
            }
        }
    }
    cout << sol;
}

 

추가적으로 미세먼지가 정말 없어졌으면 좋겠다.

하늘 볼 때 누런색이면 내 기분도 누레진다.