미세먼지 (feat. 백준, 17144번)

미세먼지
https://www.acmicpc.net/problem/17144

17144번: 미세먼지 안녕!

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/17144
#include <iostream>
#include <queue>

using namespace std;

struct Position
{
	int x, y;
};
int R, C, T;
int dx[4], dy[4];
int air_cleaner[2];
short map[51][51];
short tmp[51][51];

void spread_fine_dust()
{
	queue<Position> q;
	for (int ix = 0, iy; ix < R; ++ix)
		for (iy = 0; iy < C; ++iy)
			if (map[ix][iy] > 0)
				q.push(Position{ ix,iy });

	auto dust_value = 0, dust_count = 0;
	while (!q.empty())
	{
		auto& dust = q.front(); q.pop();
		dust_value = map[dust.x][dust.y] / 5, dust_count = 0;
		for (int idx = 0, nx, ny; idx < 4; ++idx) {
			nx = dust.x + dx[idx], ny = dust.y + dy[idx];
			if (0 <= nx && nx < R && 0 <= ny && ny < C && map[nx][ny] != -1)
				tmp[nx][ny] += dust_value, ++dust_count;
		}
		if (dust_count > 0)
			map[dust.x][dust.y] -= dust_value * dust_count;
	}
	for (int ix = 0, iy; ix < R; ++ix)
		for (iy = 0; iy < C; ++iy)
			map[ix][iy] += tmp[ix][iy], tmp[ix][iy] = 0;
}

void run_air_cleaner()
{
	// 위쪽 바람
	auto pos_x = air_cleaner[0];
	// 바람 ↓ 방향
	for (auto ix = pos_x; ix > 0; --ix)
		swap(map[ix][0], map[ix - 1][0]);
	// 바람 ← 방향
	for (auto iy = 0; iy < C - 1; ++iy)
		swap(map[0][iy], map[0][iy + 1]);
	// 바람 ↑ 방향
	for (auto ix = 0; ix < pos_x; ++ix)
		swap(map[ix][C - 1], map[ix + 1][C - 1]);
	// 바람 → 방향
	for (auto iy = C - 1; iy > 0; --iy)
		swap(map[pos_x][iy], map[pos_x][iy - 1]);
	map[pos_x][1] = 0;			// 공기청정기에 들어가 사라질 값
	// 아래쪽 바람
	pos_x = air_cleaner[1];
	// 바람 ↑ 방향
	for (auto ix = pos_x; ix < R - 1; ++ix)
		swap(map[ix][0], map[ix + 1][0]);
	// 바람 ← 방향
	for (auto iy = 0; iy < C - 1; ++iy)
		swap(map[R - 1][iy], map[R - 1][iy + 1]);
	// 바람 ↓ 방향
	for (auto ix = R - 1; ix > pos_x; --ix)
		swap(map[ix][C - 1], map[ix - 1][C - 1]);
	// 바람 → 방향
	for (auto iy = C - 1; iy > 0; --iy)
		swap(map[pos_x][iy], map[pos_x][iy - 1]);
	map[pos_x][1] = 0;			// 공기청정기에 들어가 사라질 값
}

int main()
{
	ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
	dx[0] = 1, dx[1] = -1, dx[2] = 0, dx[3] = 0;
	dy[0] = 0, dy[1] = 0, dy[2] = 1, dy[3] = -1;
	auto air_cleaner_pos = 0;
	cin >> R >> C >> T;
	for (int ix = 0, iy; ix < R; ++ix)
		for (iy = 0; iy < C; ++iy) {
			cin >> map[ix][iy], tmp[ix][iy] = 0;
			if (map[ix][iy] == -1)
				air_cleaner[air_cleaner_pos++] = ix;
		}

	for (auto idx = 0; idx < T; ++idx) {
		spread_fine_dust();
		run_air_cleaner();
	}

	auto result = 0;
	for (int ix = 0, iy; ix < R; ++ix)
		for (iy = 0; iy < C; ++iy)
			if (map[ix][iy] > 0)		result += map[ix][iy];

	cout << result << endl;
	return 0;
}
// *&)*@*

1. 미세먼지가 퍼질때는 해당 칸이 0이 아니더라도 퍼져야 합니다. 각각의 미세먼지에 대해서 모두 퍼트리고난 이후에 합산해줘야 합니다. (기존 미세먼지도 다른 미세먼지에 의해서 값이 더해질 수 있습니다.)
2. 공기청정기가 도는 방향의 마지막부터 역순으로 간다고 생각하면, 단순히 swap으로 해결할 수 있습니다. 단, 공기청정기의 위쪽 바람을 예로 들면, 공기청정기의 바로 위의 값이 전체 swap 이후 공기청정기의 위치에 오게 됩니다. (없어져야할 값이지만 -1이 있던 위치에 있으니 이점만 생각하시면 됩니다.)