[백준 17144] 미세먼지 안녕!

문제 바로가기

17144번: 미세먼지 안녕!

까다로운 문제였다

푸는 데 두시간 걸림 ㅜㅅㅜ

노잼....

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>

using namespace std;

int R, C, T;
int map[50][50];
int new_map[50][50];
int dir[50][50];
int pos[4][2] = { {1,0},{-1,0},{0,1},{0,-1} }; //아래, 위, 오, 왼
int dust_cnt;
vector<int> clean; //0: up, 1: down

bool isIn(int x, int y)
{
	if (x >= 0 && x < C && y >= 0 && y < R)
		return true;
	else
		return false;
}

void rotate()
{
	for (int i = 1; i < C - 1; i++)
	{
		dir[clean[0]][i] = 2;
		dir[clean[1]][i] = 2;
	}

	
	for (int i = 0; i < R - 1; i++)
	{
		if (i < clean[0])
			dir[i][0] = 0;
		else if (i >= clean[1])
			dir[i][C-1] = 0;
	}
	
	for (int i = 1; i < R; i++)
	{
		if (i > clean[1])
			dir[i][0] = 1;
		else if (i <= clean[0])
			dir[i][C-1] = 1;
	}

	for (int i = 1; i < C; i++)
	{
		dir[0][i] = 3;
		dir[R-1][i] = 3;
	}
}

void change_map()
{
	memset(new_map, 0, sizeof(new_map));

	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			int nx = j + pos[dir[i][j]][1];
			int ny = i + pos[dir[i][j]][0];

			if (isIn(nx, ny))
			{
				if (map[ny][nx] == -1)
					new_map[ny][nx] = -1;
				else
					new_map[ny][nx] = map[i][j];
			}
				
		}
	}

	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			map[i][j] = new_map[i][j];
			if(map[i][j] != -1)
				dust_cnt += map[i][j];
			new_map[i][j] = 0;
		}
	}
}
int main()
{
	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)
				clean.push_back(i);
		}
			
	}
	memset(dir, -1, sizeof(dir));
	rotate();

	for (int t = 0; t < T; t++)
	{
		dust_cnt = 0;
		
		for (int i = 0; i < R; i++)
		{
			for (int j = 0; j < C; j++)
			{
				if (map[i][j] > 0)
				{
					int cnt = 0;
					for (int k = 0; k < 4; k++)
					{
						int nx = j + pos[k][1];
						int ny = i + pos[k][0];

						if (isIn(nx, ny) && map[ny][nx] != -1)
						{
							new_map[ny][nx] += map[i][j] / 5;
							cnt++;
						}
					}
					new_map[i][j] -= cnt * (map[i][j] / 5);
				}
			}
		}
		for (int i = 0; i < R; i++)
		{
			for (int j = 0; j < C; j++)
			{
				map[i][j] += new_map[i][j];
			}
		}
		change_map();
	}

	cout << dust_cnt << endl;
}