[BOJ 17144] 미세먼지 안녕!

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

17144번: 미세먼지 안녕!

---

위 문제는 1초마다 미세먼지가 상하좌우로 확산되고, 공기청정기에서 바람이 나와서 미세먼지를 청소한다.

 

T초가 지났을 때의 미세먼지의 총량을 구하는 문제이다.

 

1. 공기청정기의 위치를 구함.

2. 총 T번 동안 미세먼지를 확산시키고, 공기청정기에서 바람을 내보냄 

     2-1. 임의의 배열을 만들어 미세먼지가 확산되는 정보를 저장하고, 이를 원본 배열에 적용

     2-2. 공기청정기로 바람이 들어오는 부분부터 탐색을 하면서 미세먼지를 이동시킴

3. 맵 전체를 탐색해서 미세먼지의 양을 구함

---

#include <stdio.h>

int a[51][51];
int R, C, T;

int air[2] = { -1, -1 };

void Update()
{
	int _a[51][51] = { 0, };


	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			int l = a[i][j] / 5;
			for (int k = -1; k <= 1; k += 2)
			{
				if (i + k >= 0 && i + k < R && a[i + k][j] != -1)
				{
					_a[i + k][j] += l;
					a[i][j] -= l;
				}
				if (j + k >= 0 && j + k < C && a[i][j + k] != -1)
				{
					_a[i][j + k] += l;
					a[i][j] -= l;
				}
			}
		}
	}
	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			a[i][j] += _a[i][j];
		}
	}

	int _x , _y;
	int d[2][4][2] = {
		{{0, -1}, {1, 0}, {0, 1}, {-1, 0}},
		{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}
	};

	int _i = 0;
	for (int i = 0; i < 2; i++)
	{
		_x = 0, _y = air[i], _i = 0;
		do
		{
			if (_x + d[i][_i][0] < 0 || _y + d[i][_i][1] < 0 ||
				_x + d[i][_i][0] >= C || _y + d[i][_i][1] >= R || (i == 0 && _y + d[i][_i][1] > air[i]) || (i == 1 && _y + d[i][_i][1] < air[i]))
				_i++;

			if (a[_y][_x] == -1)
				a[_y + d[i][_i][1]][_x + d[i][_i][0]] = 0;
			else
				a[_y][_x] = a[_y + d[i][_i][1]][_x + d[i][_i][0]];
			_x += d[i][_i][0];
			_y += d[i][_i][1];
		} while (a[_y][_x] != -1);

		a[_y - d[i][_i][1]][_x - d[i][_i][0]] = 0;
	}
}

int main(){

	scanf("%d %d %d", &R, &C, &T);

	for (int i = 0; i < R; i++)
		for (int j = 0; j < C; j++)
		{
			scanf("%d", &a[i][j]);
			if (air[0] == -1 && a[i][j] == -1)
			{
				air[0] = i;
				air[1] = i + 1;
			}
		}

	while (T--)
	{
		Update();
	}
	int sum = 0;

	for (int i = 0; i < R; i++)
		for (int j = 0; j < C; j++)
			if(a[i][j] != -1)
				sum += a[i][j];

	printf("%d", sum);
}