백준 17144번 _ 미세먼지 안녕!

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

17144번: 미세먼지 안녕!

 

1. 풀이방법

 

 그냥 구현만 하면 되는 문제다.

 하지만, 주의할점이 몇가지 있는데 확산시킬때 계산할 map과 확산시킬 기준이 되는 map 두개의 map을 준비해서 풀어야 오류가 없다.

 그리고 공기청정기의 경로를 미리 순서대로 저장시켜놓고 사용하면 간편하다.

 

 

 

---

 

 2. 코드

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int map[52][52];
int calmap[52][52];
vector<pair<int, int>> ueraseDustLine;
vector<pair<int, int>> deraseDustLine;
vector<int> airCleanerPosY;
int r, c, t;

void calMapInit()
{
	for (int i = 0; i < r; i++)
		for (int j = 0; j < c; j++)
			calmap[i][j] = map[i][j];
}

void mapUpdate()
{
	for (int i = 0; i < r; i++)
		for (int j = 0; j < c; j++)
			map[i][j] = calmap[i][j];
}

void makeEraseDustLine()
{
	int upY = airCleanerPosY[0];
	int downY = airCleanerPosY[1];

	for (int j = 1; j < c-1; j++)
	{
		ueraseDustLine.push_back({ upY, j });
		deraseDustLine.push_back({ downY, j });
	}

	for (int i = upY; i > 0; i--)
		ueraseDustLine.push_back({ i, c - 1 });

	for (int i = downY; i < r - 1; i++)
		deraseDustLine.push_back({ i, c - 1 });

	for (int j = c - 1; j > 0; j--)
	{
		ueraseDustLine.push_back({ 0, j });
		deraseDustLine.push_back({ r - 1, j });
	}

	for (int i = 0; i < upY; i++)
		ueraseDustLine.push_back({ i, 0 });

	for (int i = r - 1; i > downY; i--)
		deraseDustLine.push_back({ i, 0 });
}

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

void diffusion(int y, int x)
{
	int source = map[y][x];
	int cnt = 0;
	for (int i = 0; i < 4; i++)
	{
		int ty = y + dy[i];
		int tx = x + dx[i];

		if (ty >= 0 && tx >= 0 && ty < r && tx < c)
		{
			if (map[ty][tx] == -1)
				continue;
			calmap[ty][tx] += (source / 5);
			cnt++;
		}
	}
	calmap[y][x] = calmap[y][x] - ((source / 5) * cnt);
}

void play()
{
	calMapInit();
	//diffusion
	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			if (map[i][j] != -1 && map[i][j] > 0)
			{
				diffusion(i, j);
			}
		}
	}
	mapUpdate();

	////clean
	for (int i = (int)ueraseDustLine.size() - 1; i > 0; i--)
	{
		int y = ueraseDustLine[i].first;
		int x = ueraseDustLine[i].second;
		int cy = ueraseDustLine[i - 1].first;
		int cx = ueraseDustLine[i - 1].second;

		map[y][x] = map[cy][cx];
		if (i == 1)
			map[cy][cx] = 0;
	}

	for (int i = (int)deraseDustLine.size() - 1; i > 0; i--)
	{
		int y = deraseDustLine[i].first;
		int x = deraseDustLine[i].second;
		int cy = deraseDustLine[i - 1].first;
		int cx = deraseDustLine[i - 1].second;

		map[y][x] = map[cy][cx];
		if (i == 1)
			map[cy][cx] = 0;
	}
}

int countDust()
{
	int cnt = 0;
	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			if (map[i][j] > 0)
				cnt += map[i][j];
		}
	}
	return cnt;
}

void solve()
{
	for (int i = 0; i < t; i++)
	{
		play();
	}
	cout << countDust();
}

int main()
{
	cin >> r >> c >> t;
	int value;
	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			cin >> value;
			map[i][j] = value;
			if (value == -1)
				airCleanerPosY.push_back(i);
		}
	}
	makeEraseDustLine();
	//solve
	solve();

	return 0;
}

 

---

 

3. 후기

 

그나마 괜찮았다.