17144번 미세먼지 안녕!

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

요즘 SW 역량 테스트에 자주 등장하는 유형인 시뮬레이션 문제이다.

딱히 알고리즘의 사용없이 그냥 문제 그대로 구현하면 된다.

나는 생각보다 빠르게 풀고, 예제들을 입력해보았는데

모든 예제들의 답이 188로 일정하게 나왔었다.

그래서 처음에는 

diffusion[i][j] += dust[i][j] - (dust[i][j] / 5) * cnt;
 
또는
 
diffusion[i][j] += dust[i][j] - (dust[i][j] * cnt) / 5;

위에 있는 것 중 아래 것을 생각을 했으나, 문제를 읽어보니 그게 아니었다.(위의 것이 맞음)

그래서 마음을 가다듬고(?), 천천히 생각해보니

air() 함수 내의 67번 째 줄 코드와 82번 째 줄 코드를 안 써줬다.

다시 말하면, 

반시계 방향을 보자면,

나는 

dust[sy][sx]에 dust[sy-1][sx] 대입,

dust[sy-1][sx]에 dust[sy-2][sx] 대입 ... (sx는 0이다)

이런 식으로 진행하다가

마지막에 (75번 째 줄 코드 for문의 마지막 순서 i가 C-2일 때)

dust[sy][1] = dust[sy][0];

위의 것이 실행되는데, dust[sy][0]에 dust[sy-1][sx]를 대입한 적이 있어

dust[sy-1][0]의 값이 dust[sy][1]에 대입되는 오류가 발생하는 것이었다.

이를 방지하기 위해, 67번 째 줄 코드와 82번 째 줄 코드를 추가해줬다.

그리고 정말로 미세먼지는 안녕이었으면 좋겠다.

정답 코드

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <sstream>
#include <tuple>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
 
int diffusion[51][51] = { 0, }, dust[51][51] = { 0, };
 
int sy = 0, sx = 0, ey = 0, ex = 0, R = 0, C = 0, T = 0;
 
void spread()
{
    memset(diffusion, 0, sizeof(diffusion));
 
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
            if (dust[i][j] > 0)
            {
                int cnt = 0;
 
                for (int d = 0; d < 4; d++)
                {
                    int y = i + dy[d];
                    int x = j + dx[d];
 
                    if (y < 0 || y >= R || x < 0 || x >= C || dust[y][x] == -1) continue;
 
                    ++cnt;
 
                    diffusion[y][x] += dust[i][j] / 5;
                }
 
                diffusion[i][j] += dust[i][j] - (dust[i][j] / 5) * cnt;
            }
 
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)    
            dust[i][j] = diffusion[i][j];    
 
    dust[sy][sx] = dust[ey][ex] = -1;
}
 
void air()
{
    dust[sy][sx] = dust[ey][ex] = 0;
 
    // 반시계
    for (int i = sy; i >= 1; i--)
        dust[i][0] = dust[i - 1][0];
    
    dust[sy][sx] = 0; // 이 코드를 안 써줬었다.
 
    for (int i = 0; i < C - 1; i++)
        dust[0][i] = dust[0][i + 1];
    
    for (int i = 0; i < sy; i++)
        dust[i][C - 1] = dust[i + 1][C - 1];
    
    for (int i = 0; i < C - 1; i++)
        dust[sy][C - 1 - i] = dust[sy][C - 2 - i];
 
    // 시계
    for (int i = ey; i < R - 1; i++)
        dust[i][0] = dust[i + 1][0];
    
    dust[ey][ex] = 0; // 이 코드를 안 써줬었다.
 
    for (int i = 0; i < C - 1; i++)
        dust[R - 1][i] = dust[R - 1][i + 1];
 
    for (int i = R - 1; i >= ey + 1; i--)
        dust[i][C - 1] = dust[i - 1][C - 1];    
 
    for (int i = C - 1; i >= 1; i--)
        dust[ey][i] = dust[ey][i - 1];
 
    dust[sy][sx] = dust[ey][ex] = -1;
}
 
void simulation()
{
    while (T--)
    {
        spread();
        air();
    }
}
 
int remain()
{
    int ret = 0;
 
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
            if (dust[i][j] > 0) 
                ret += dust[i][j];
 
    return ret;
}
 
int main(void)
{
    bool d = true;
    
    scanf("%d %d %d", &R, &C, &T);
 
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
        {
            scanf("%d", &dust[i][j]);
 
            if (dust[i][j] == -1)
            {
                if (d)
                {
                    sy = i; sx = j;
                    d = false;
                }
                else ey = i; ex = j;            
            }
        }
            
 
    simulation();
    
    printf("%d\n", remain());
 
    return 0;
}