[BOJ]백준 17144번: 미세먼지 안녕!
https://www.acmicpc.net/problem/17144
17144번: 미세먼지 안녕!
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 공기청정기는 항상 왼쪽 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼
www.acmicpc.net
전형적인 단계별로 구현하는 문제!!
초기 상태가 주어졌을 때, 각 칸에는 미세먼지의 양이 써져있고, 1초 동안엔 아래의 루틴이 일어난다
- 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
- 각 칸의 미세먼지는 인접한 네 방향으로 확산된다.
- 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
- 확산되는 양은 Ar,c/5의 정수형이다.
- (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.
- 공기청정기가 작동한다.
- 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
- 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
- 공기청정기에서 부는 바람은 깨끗한 바람이고, 공기청정기로 들어간 미세먼지는 없어진다.
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;
}확산 자체는 어렵지 않아 금방 구현했지만 생각보다 먼지 확산하는게 너무 오래걸렸다....
ㅠㅡㅜ