Baekjoon 17144번 미세먼지 안녕!

문제

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

걸린 시간

01 : 46 : 42

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int r, c, t, A;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1}; // N E S W
int dr[4] = {-1, 1, -1, 1}; // S E N W
int before[50][50], after[50][50];
vector<pair<int, int>> robot;

void diffusion(){
    for(int y = 0; y < r; y++){
        for(int x = 0; x < c; x++){
            if(before[y][x] <= 0) continue;
            for(int i = 0; i < 4; i++){
                int ny = y+dy[i];
                int nx = x+dx[i];
                if(0 <= ny && ny < r && 0 <= nx && nx < c && before[ny][nx] != -1){
                    after[ny][nx] += before[y][x]/5;
                    after[y][x] -= before[y][x]/5;
                }
            }
        }
    }
    for(int y = 0; y < r; y++)
        for(int x = 0; x < c; x++)
            before[y][x] = after[y][x];
}

void cleaning(){
    int cy, cx, ny, nx;
    // up
    cy = robot[0].first;
    cx = robot[0].second;
    ny = cy;
    nx = cx;
    for(int i = 0; i < 4; i++){
        while(true){
            ny = cy+dy[i];
            nx = cx+dx[i];
            if(0 > ny || robot[0].first+1 <= ny || 0 > nx || c <= nx) break;
            // 시작 지점일 때
            if(before[cy][cx] == -1){
                cy = ny;
                cx = nx;
                continue;
            }
            // 마지막 지점일 때
            if(before[ny][nx] == -1){
                before[cy][cx] = 0;
                cy = ny;
                cx = nx;
                continue;
            }
            // 인접한 칸 일 때
            before[cy][cx] = before[ny][nx];
            cy = ny;
            cx = nx;
        }
    }
    // down
    cy = robot[1].first;
    cx = robot[1].second;
    ny = cy;
    nx = cx;
    for(int i = 0; i < 4; i++){
        while(true){
            ny = cy+dy[i]*dr[i];
            nx = cx+dx[i]*dr[i];
            if(robot[1].first > ny || r <= ny || 0 > nx || c <= nx) break;
            // 시작 지점일 때
            if(before[cy][cx] == -1){
                cy = ny;
                cx = nx;
                continue;
            }
            // 마지막 지점일 때
            if(before[ny][nx] == -1){
                before[cy][cx] = 0;
                cy = ny;
                cx = nx;
                continue;
            }
            // 인접한 칸 일 때
            before[cy][cx] = before[ny][nx];
            cy = ny;
            cx = nx;
        }
    }
    for(int y = 0; y < r; y++)
        for(int x = 0; x < c; x++)
            after[y][x] = before[y][x];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> r >> c >> t;
    for(int y = 0; y < r; y++){
        for(int x = 0; x < c; x++){
            cin >> A;
            before[y][x] = after[y][x] = A;
            if(A == -1) robot.push_back(make_pair(y, x));
        }
    }
    while(t--){
        diffusion();
        cleaning();
    }
    int ans = 0;
    for(int y = 0; y < r; y++)
        for(int x = 0; x < c; x++)
            if(before[y][x] > 0) ans += before[y][x];
    cout << ans;
    return 0;
}

좌표의 범위 설정, 갱신 부분의 구현이 꼼꼼하지 못해 문제풀이에 시간이 많이 걸렸다.