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

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

17144번: 미세먼지 안녕!

전형적인 단계별로 구현하는 문제!!

초기 상태가 주어졌을 때, 각 칸에는 미세먼지의 양이 써져있고, 1초 동안엔 아래의 루틴이 일어난다

 

초기상태

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

맵 내부에서만 확산이 일어난다

사방으로 확산 일어남

공기청정기가 있는 칸으로는 확산X

이러한 방향으로 확산이 일어남

void dust(좌표){

  네 방향을 탐색:

    다음 위치가 맵 내부이고 공기청정기가 없다면:

      q에 푸시

}

좌표 구조체point와 int형으로 이루어진 큐 q는 새로 확산될 좌표와 추가될 먼지의 양을 저장한다

void airclean(좌표, 청소방향){

  dx, dy배열을 이용 해당 방향에 있는 다음 칸을 탐색:

    다음 칸에 있는 먼지의 양을 임시저장

    현재 칸(이전칸)에 있는 먼지의 양을 다음 칸으로 옮김

    칸 이동

}

#include <cstdio>
#include <queue>
#include <vector>
#define safe(x,y) x>=0&&x<c&&y>=0&&y<r
using namespace std;
struct point { int x, y; };
int r, c, t, ans, d, a[1001][1001], dx[] = { 1,0,-1,0 }, dy[2][4] = { {0,-1,0,1},{0,1,0,-1} };
queue<pair<point, int>> q;
vector<point> v;
void dust(int x, int y) {
	int &s = a[y][x]; d = 0;
	for (int i = 0, nx, ny; i < 4; i++) {
		nx = x + dx[i]; ny = y + dy[0][i];
		if (safe(nx, ny) && a[ny][nx] != -1) {
			q.push({ {nx,ny},s / 5 });
			d++;
		}
	}
	s -= (s / 5)*d;
}
void airclean(int x, int y, int dir) {
	point cur = { x,y }, n = { x + 1,y }, temp = n;
	for (int i = 0, pre = 0, post; i < 4; i++) {
		n = { cur.x + dx[i],cur.y + dy[dir][i] };
		while (safe(n.x, n.y)) {
			if (!dir&&n.y > y)break;
			if (dir&&n.y < y)break;		
			post = a[n.y][n.x];
			a[n.y][n.x] = pre;
			pre = post; if (safe(n.x, n.y))cur = n;
			n = { cur.x + dx[i % 4],cur.y + dy[dir][i] };
		}
	}
}
int main() {
	freopen("input.txt", "r", stdin);
	scanf("%d%d%d", &r, &c, &t);
	for (int i = 0; i < r; i++)for (int j = 0; j < c; j++) {
		scanf("%d", &a[i][j]);
		if (a[i][j] == -1)v.push_back({ j,i });
	}
	for (int i = 0; i < t; i++) {
		for (int i = 0; i < r; i++)
			for (int j = 0; j < c; j++) {
				if (a[i][j] > 0)dust(j, i);
			}
		while (!q.empty()) {
			point p = q.front().first;
			int s = q.front().second; q.pop();
			a[p.y][p.x] += s;
		}
		airclean(v[0].x, v[0].y, 0);
		airclean(v[1].x, v[1].y, 1);
	}
	for (int l = 0; l < r; l++)
		for (int j = 0; j < c; j++)ans += a[l][j];
	printf("%d", ans + 2);
	return 0;
}

확산 자체는 어렵지 않아 금방 구현했지만 생각보다 먼지 확산하는게 너무 오래걸렸다....

ㅠㅡㅜ