백준 17144 - 미세먼지 안녕!(골드4)

문제

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

접근법

미세먼지가 어떤 식으로 확산되는 지 헷갈려서 푸는데 시간이 좀 걸렸다.
우선 미세먼지의 확산은 모든 칸에서 동시에 일어난다.
따라서 그냥 미세먼지를 확산시키면 주변 칸에 영향을 주고 그 영향을 받은 칸에서 확산을 하면 문제의 예시와 다르게 나온다.
따라서 모든 칸의 확산으로 인한 변화량을 미리 저장해두고 한번에 적용시켜야한다.
그래서 나는 확산 변화량을 임시배열에 저장하고 모든 칸의 확산 후 임시배열의 내용을 적용시켰다.
그 후 공기청정기의 작동은 무식하게 구현했다.

구현

#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
int R,C,T;
int map[51][51];
int tmpmap[51][51];
int dy[4]={0,0,-1,1};
int dx[4]={-1,1,0,0};
vector<pair<int, int> > v;
int uprow,upcol,downrow,downcol;
void move()
{
	for(int i=uprow-1;i>=1;i--)
	{
		if(map[i+1][1]==-1)
		{
			map[i][1]=0;
		}
		else
		{
			map[i+1][1]=map[i][1];
		}
	}
	
	for(int i=2;i<=C;i++)
	{
		map[1][i-1]=map[1][i];
	}
	
	for(int i=2;i<=uprow;i++)
	{
		map[i-1][C]=map[i][C];
	}
	
	for(int i=C-1;i>=2;i--)
	{
		map[uprow][i+1]=map[uprow][i];
		map[uprow][i]=0;
	}
	
	
	for(int i=downrow+1;i<=R;i++)
	{
		if(map[i-1][1]==-1)
		{
			map[i][1]=0;
		}
		else
		{
			map[i-1][1]=map[i][1];
		}
	}
	
	for(int i=2;i<=C;i++)
	{
		map[R][i-1]=map[R][i];
	}
	
	for(int i=R-1;i>=downrow;i--)
	{
		map[i+1][C]=map[i][C];
	}
	
	for(int i=C-1;i>=2;i--)
	{
		map[downrow][i+1]=map[downrow][i];
		map[downrow][i]=0;
	}
}
int main()
{
	
	scanf("%d %d %d",&R,&C,&T);
	for(int i=1;i<=R;i++)
	{
		for(int j=1;j<=C;j++)
		{
			scanf("%d",&map[i][j]);
			if(map[i][j]==-1)
			{
				v.push_back(make_pair(i,j));
			}
		}
	}
	uprow=v[0].first;
	upcol=v[0].second;
	downrow=v[1].first;
	downcol=v[1].second;
	for(int k=0;k<T;k++)
	{
		memset(tmpmap,0,sizeof(tmpmap));
		for(int i=1;i<=R;i++)
		{
			for(int j=1;j<=C;j++)
			{
				int cnt=0;
				if(map[i][j]!=0)
				{
					
					for(int d=0;d<4;d++)
					{
						int r=i+dy[d];
						int c=j+dx[d];
						
						if(r<1 || r>R || c<1 || c>C || map[r][c]==-1)
							continue;
						
						tmpmap[r][c]+=map[i][j]/5;
						cnt++;
					}
				}
				tmpmap[i][j]+=map[i][j]-(map[i][j]/5)*cnt;
			}
		}
		memcpy(map,tmpmap,sizeof(tmpmap));
		
		move();
		
		
	}
	int cnt=0;
	for(int i=1;i<=R;i++)
	{
		for(int j=1;j<=C;j++)
		{
			if(map[i][j]!=-1)
				cnt+=map[i][j];
		}
	}
	printf("%d",cnt);
	return 0;
}