17144 미세먼지 안녕!

www.acmicpc.net/problem/17144

17144번: 미세먼지 안녕!

(문제 풀이)

이 문제는 별 다른 시간복잡도와 알고리즘의 사용을 요구하지 않는다. 

시뮬레이션 구현의 문제이다.

하나씩 어떻게 동작하는지 예제 그림의 도움을 최대한 받아서 하나씩 따라가며 시작해본다.

1. 확산을 하고

2. 공기청정기의 위 아래 기준으로 배열의 값들을 회전시킨다.  

그렇다면,

 

1. 확산을 어떻게 시킬것인가

• 모든 먼지가 있는 칸에 확산되는 값들과, 감소되는 기존 미세먼지 중심의 감소값을 따로 Copy 배열을만들어 추가시키김 (r행,c열) 까지 검사가 끝난후 확산 값들의 누적 값을 기존 map에 더해준다.

 

2. 회전 시키는 방법.

• 문제 조건에 맞게 cw인지 ccw인지 보고 회전을 시킨다.

• 공기청정기로 먼지가 들어가면 해당 숫자는 제거된다.

 

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

int map[50][50];
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };

int ccw_dx[] = { 0,-1,0,1 };
int ccw_dy[] = { 1,0,-1,0 };

int cw_dx[] = { 0,1,0,-1 };
int cw_dy[] = { 1,0,-1,0 };
int R, C, T;
vector<pair<int, int>> cleaner;
void Input();
void Solve();
void Spread_dust();
void go_Cleaner(int x, int y,char ch);
int ans;
int main(void)
{
	Input();
	Solve();
	return 0;
}

void Solve()
{
	for (int i = 0; i < T; ++i)
	{
		Spread_dust();
		go_Cleaner(cleaner[0].first, cleaner[0].second,'t');
		go_Cleaner(cleaner[1].first, cleaner[1].second, 'b');
	}
	for (int i = 0; i < R; ++i)
	{
		for (int j = 0; j < C; ++j)
		{
			if (map[i][j]==-1)continue;
			
			ans += map[i][j];
		}
	}
	cout << ans << '\n';
}
void go_Cleaner(int x, int y, char ch)
{
	int copy_map[50][50];
	for (int i = 0; i < R; ++i)
	{
		for (int j = 0; j < C; ++j)
			copy_map[i][j] = map[i][j];
	}
	if (ch == 't') //ccw
	{
		int xn = x;
		int yn = y + 1;
		map[xn][yn] = 0;
		for (int i = 0; i < 4; ++i)
		{
			while (true)
			{	
				int cur_x = xn;
				int cur_y = yn;
				xn +=  ccw_dx[i];
				yn +=  ccw_dy[i];

				if (xn < 0 || xn >= R || yn < 0 || yn >= C)
				{
					xn -= ccw_dx[i];
					yn -= ccw_dy[i];
					break;
				}

				if (xn == x && yn == y) //청소기 있는곳에 도착했을때
					break;

				map[xn][yn] = copy_map[cur_x][cur_y];
			}
		}
	}
	else
	{
		int xn = x;
		int yn = y + 1;
		map[xn][yn] = 0;
		for (int i = 0; i < 4; ++i)
		{
			while (true)
			{
				int cur_x = xn;
				int cur_y = yn;
				xn += cw_dx[i];
				yn += cw_dy[i];

				if (xn < 0 || xn >= R || yn < 0 || yn >= C)
				{
					xn -= cw_dx[i];
					yn -= cw_dy[i];
					break;
				}

				if (xn == x && yn == y) //청소기 있는곳에 도착했을때
					break;

				map[xn][yn] = copy_map[cur_x][cur_y];
			}
		}
	}
	
}
void Spread_dust()
{
	int copy_map[50][50];
	memset(copy_map, 0, sizeof(copy_map));

	for (int i = 0; i < R; ++i)
	{
		for (int j = 0; j < C; ++j)
		{
			if (map[i][j] != 0 && map[i][j] != -1) //먼지인 경우
			{
				for (int k = 0; k < 4; ++k)
				{
					int xn = i + dx[k]; //확산 되는 x좌표
					int yn = j + dy[k]; //확산 되는 y좌표

					if (xn >= 0 && xn < R && yn >= 0 && yn < C)
					{
						if (map[xn][yn] != -1) //청소기가 아닌경우
						{
							int sp_dust = map[i][j] / 5;
							copy_map[i][j] -= sp_dust;
							copy_map[xn][yn] += sp_dust;
						}
					}
				}
			}
		}
	}

	for (int i = 0; i < R; ++i)
	{
		for (int j = 0; j < C; ++j)
			map[i][j] += copy_map[i][j];
	}
}
void Input()
{
	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)
				cleaner.push_back(make_pair(i, j));
		}
	}
}