[백준/BOJ] 백준 17144번 : 미세먼지 안녕!

www.acmicpc.net/problem/17144

17144번: 미세먼지 안녕!

미세먼지를 확산하는 함수를 만들고, 공기청정기를 작동하는 함수를 만들어 미세먼지가 확산하고 공기청정기가 작동하는 것을 t번 반복한다. 공기 청정기를 작동은 공기청정기에 먼저 들어오는 미세먼지 순으로 deque에 저장하고, pop_front(); push_back(0);을 해서 공기청정기가 정화하는 것과, 공기청정기에서 바람이 나오는 것을 적용한다. 그렇게 움직여진 미세먼지를 board에 적용한다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <deque>
using namespace std;

int r, c, t;
pair<int, int> cleaner1;
pair<int, int> cleaner2;
bool in_cleaner1 = false;
int board[50][50];
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

//공기청정기 확산
void Spread()
{
	//확산으로 인해 더해지는 미세먼지들을 저장
	vector<vector<int>> add_board(r, vector<int>(c, 0));

	for (int i = 0; i < r; i++)
		for (int j = 0; j < c; j++)
		{
			pair<int, int> here = make_pair(i, j);
			int here_spread_cnt = 0; //확산되는 개수

			for (int i = 0; i < 4; i++)
			{
				pair<int, int> there = make_pair(here.first + dxdy[i][0], here.second + dxdy[i][1]);

				//there지점에 미세먼지 확산이 가능할때
				if (there.first >= 0 && there.first < r && there.second >= 0 && there.second < c && board[there.first][there.second] != -1)
				{
					add_board[there.first][there.second] += board[here.first][here.second] / 5;
					here_spread_cnt++;
				}
			}

			board[here.first][here.second] -= (board[here.first][here.second] / 5) * here_spread_cnt;
		}

	//board에 확산되는 미세먼지들을 더한다
	for (int i = 0; i < r; i++)
		for (int j = 0; j < c; j++)
			board[i][j] += add_board[i][j];
}

//공기청정기 작동
void Clean()
{
	deque<int> dust1; //cleaner1로 인해 이동하는 미세먼지들을 cleaner1에 먼저 들어오는거 순으로 저장
	deque<int> dust2; //cleaner2로 인해 이동하는 미세먼지들을 cleaner2에 먼저 들어오는거 순으로 저장

	for (int i = cleaner1.first - 1; i >= 0; i--)
		dust1.push_back(board[i][0]);
	for (int j = 1; j < c; j++)
		dust1.push_back(board[0][j]);
	for (int i = 1; i <= cleaner1.first; i++)
		dust1.push_back(board[i][c - 1]);
	for (int j = c - 2; j > 0; j--)
		dust1.push_back(board[cleaner1.first][j]);

	dust1.pop_front(); //먼저 들어온거를 뺴낸다(공기청정기가 정화)
	dust1.push_back(0); //공기청정기에서 바람이 나오는것

	//움직인 먼지를 board에 적용한다
	for (int i = cleaner1.first - 1; i >= 0; i--)
	{
		board[i][0] = dust1[0];
		dust1.pop_front();
	}
	for (int j = 1; j < c; j++)
	{
		board[0][j] = dust1[0];
		dust1.pop_front();
	}
	for (int i = 1; i <= cleaner1.first; i++)
	{
		board[i][c - 1] = dust1[0];
		dust1.pop_front();
	}
	for (int j = c - 2; j > 0; j--)
	{
		board[cleaner1.first][j] = dust1[0];
		dust1.pop_front();
	}

	for (int i = cleaner2.first + 1; i < r; i++)
		dust2.push_back(board[i][0]);
	for (int j = 1; j < c; j++)
		dust2.push_back(board[r - 1][j]);
	for (int i = r - 2; i >= cleaner2.first; i--)
		dust2.push_back(board[i][c - 1]);
	for (int j = c - 2; j > 0; j--)
		dust2.push_back(board[cleaner2.first][j]);

	dust2.pop_front();
	dust2.push_back(0);

	for (int i = cleaner2.first + 1; i < r; i++)
	{
		board[i][0] = dust2[0];
		dust2.pop_front();
	}
	for (int j = 1; j < c; j++)
	{
		board[r - 1][j] = dust2[0];
		dust2.pop_front();
	}
	for (int i = r - 2; i >= cleaner2.first; i--)
	{
		board[i][c - 1] = dust2[0];
		dust2.pop_front();
	}
	for (int j = c - 2; j > 0; j--)
	{
		board[cleaner2.first][j] = dust2[0];
		dust2.pop_front();
	}
}

int Solve()
{
	//미세먼지 확산, 공기청정기 작동을 t번 반복한다
	for (int i = 0; i < t; i++)
	{
		Spread();
		Clean();
	}

	int ret = 0;
	for (int i = 0; i < r; i++)
		for (int j = 0; j < c; j++)
		{
			if (board[i][j] != -1)
				ret += board[i][j];
		}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> r >> c >> t;

	for (int i = 0; i < r; i++)
		for (int j = 0; j < c; j++)
		{
			int input;

			cin >> input;

			if (input == -1) //공기청정기일때
			{
				if (in_cleaner1 == false)
				{
					cleaner1 = make_pair(i, j);
					in_cleaner1 = true;
				}

				else
					cleaner2 = make_pair(i, j);
			}

			board[i][j] = input;
		}

	cout << Solve();

	return 0;
}