백준 / 17144 미세먼지 안녕! C++

www.acmicpc.net/problem/17144

17144번: 미세먼지 안녕!

뭔가 그림만 보면 bfs 같은 걸 이용할 거 같이 생겨서 풀어봤는데 문제를 읽어보니 그냥 노가다 구현이었다.

문제 조건은 다음과 같다.

미세먼지의 양과 공기청정기의 위치가 주어졌을 때 1초동안 다음의 일이 일어난다.

 

1. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
   • (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
   • 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
   • 확산되는 양은 Ar,c/5이고 소수점은 버린다.
   • (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.
2. 공기청정기가 작동한다.
   • 공기청정기에서는 바람이 나온다.
   • 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
   • 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
   • 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.

이 때 주의해야할 것은 확산이 일어날 때 날라온 녀석을 합치면 안 된다. 처음에 날라온 녀석을 합친 후 다시 나누기 5를 해서 한 번 틀렸다.

그리고 공기청정기의 바람은 문제에 주어진대로 공기가 이동하면서 먼지를 이동시킨다. 공기의 흐름 구현만 잘 하면 어렵지 않은 문제이다.

 

코드는 다음과 같다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>

using namespace std;

int r, c, t;
int room[50][50];
int spread_dust[50][50];
int dy[4] = { 1,-1,0,0 };
int dx[4] = { 0,0,1,-1 };
pair<int, int>air1 = { -1,-1 };
pair<int, int>air2 = { -1,-1 };

void make_room()
{
	cin >> r >> c >> t;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> room[i][j];
			if (room[i][j] == -1)
			{
				if (air1.first == -1) {
					air1.first = i;
					air1.second = j;
				}
				else {
					air2.first = i;
					air2.second = j;
				}
			}
		}
	}
}

void spread()
{
	memset(spread_dust, 0, sizeof(spread_dust));
	spread_dust[air1.first][air1.second] = -1;
	spread_dust[air2.first][air2.second] = -1;

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			int dust = room[i][j];
			if (dust == 0 || dust == -1)
				continue;
			int ndust = dust / 5;
			for (int k = 0; k < 4; k++) {
				int ny = i + dy[k];
				int nx = j + dx[k];
				if (ny >= 0 && ny < r && nx >= 0 && nx < c) {
					if (room[ny][nx] != -1) {
						spread_dust[ny][nx] += ndust;
						spread_dust[i][j] -= ndust;
					}
				}
			}
		}
	}

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

void activate_up()
{
	int tmp1 = room[air1.first][c - 1];
	int tmp2 = room[0][c - 1];
	int tmp3 = room[0][0];

	for (int x = c - 2; x > air1.second; x--) {
		room[air1.first][x + 1] = room[air1.first][x];
	}
	room[air1.first][air1.second + 1] = 0;
	for (int y = 1; y < air1.first; y++) {
		room[y - 1][c - 1] = room[y][c - 1];
	}
	room[air1.first - 1][c - 1] = tmp1;
	for (int x = 0; x < c - 2; x++) {
		room[0][x] = room[0][x + 1];
	}
	room[0][c - 2] = tmp2;
	for (int y = air1.first - 1; y > 1; y--) {
		room[y][0] = room[y - 1][0];
	}
	room[1][0] = tmp3;
}

void activate_down()
{
	int tmp1 = room[air2.first][c - 1];
	int tmp2 = room[r - 1][c - 1];
	int tmp3 = room[r - 1][0];
	
	for (int x = c - 2; x > air2.second; x--) {
		room[air2.first][x + 1] = room[air2.first][x];
	}
	room[air2.first][air2.second + 1] = 0;
	for (int y = r - 1; y > air2.first + 1; y--) {
		room[y][c - 1] = room[y - 1][c - 1];
	}
	room[air2.first + 1][c - 1] = tmp1;
	for (int x = 0; x < c - 2; x++) {
		room[r - 1][x] = room[r - 1][x + 1];
	}
	room[r - 1][c - 2] = tmp2;
	for (int y = air2.first + 1; y < r - 2; y++) {
		room[y][0] = room[y + 1][0];
	}
	room[r - 2][0] = tmp3;
}

int result()
{
	int res = 0;
	for (int i = 0; i < r; i++)
		for (int j = 0; j < c; j++)
			res += room[i][j];

	res += 2; //공기청정기 -2 
	return res;
}

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

	make_room();
	while (t--) {
		spread();
		activate_up();
		activate_down();
	}
	cout << result();
}