백준 17144 - 미세먼지 안녕!

문제링크

• 백준 17144

문제설명

• RxC 크기의 격자판 모양의 집이 주어지고 각 칸 (r,c)에는 미세먼지의 양이 담겨 있다.
• 공기청정기는 항상 1번 열에 위치하고, -1로 표현한다.
• 1초 동안 아래와 같은 로직이 이루어진다.
  • 미세먼지 확산
  • (r,c)에 있는 미세먼지는 네 방향으로 확산된다.
  • 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
  • 확산되는 양은 A(r,c) /5 이고 소수점은 버린다.
  • (r,c)에 남은 미세먼지 양은 A(r,c) = A(r,c) - A(r,c)/5 * count 이다. (count는 확산된 칸의 개수)
  • 공기청정기 작동
  • 공기청정기에서 바람이 나와 미세먼지가 순환한다.
  • 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
• T 초 이후 남은 미세먼지의 양을 계산하라.

문제접근

• 공기청정기 순환 로직이 처음엔 까다롭다 생각했는데, 행(r)을 기준으로 작성하니 생각보다 간단했다.
• 편의상 공기청정기 상단 부분의 행을 x1, 하단 부분의 행을 x2라 하면 순환 로직은 아래와 같다.
  • r==1, r==R 인 경우 왼쪽방향으로 순환
  • r==x1, r==x2인 경우 오른쪽방향으로 순환
  • 1 < r < x1 인 경우 1열은 아래쪽, C열은 위쪽으로 순환
  • x2 < r < R 인 경우 1열은 위쪽, C열은 아래쪽으로 순환
  • 해당 r에 위치한 칸들은 갱신이 필요한 부분은 반드시 갱신을 해주고 넘어간다.
  • 공기청정기로 들어가는 경우는 무시한다. (미세먼지 제거)
• 확산 로직이나 공기청정기 순환 로직이나 모두 동시에 일어나야 하기 때문에 각각의 칸의 변화가 서로에게 영향을 주면 안된다. 따라서, nRoom 의 2차원 배열에만 칸의 값을 갱신해주고, 로직이 모두 수행되었을 때 room 에 덮어쓰도록 하였다.

구현

#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>
using namespace std;

int R, C, T;
int room[51][51] = { 0, };
int nRoom[51][51];
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
vector<int> airX;

// 1. 모든 미세먼지들의 확산 로직
void DustDiffustion(int xpos, int ypos) {
	int cnt = 0;
	int diffuseDust;
	for (int dir = 0; dir < 4; dir++) {
		int nextX = xpos + dx[dir];
		int nextY = ypos + dy[dir];
		if (nextX<1 || nextX>R || nextY<1 || nextY>C) continue;
		if (room[nextX][nextY] == -1) continue;
		diffuseDust = room[xpos][ypos] / 5;
		nRoom[nextX][nextY] += diffuseDust;
		cnt++;
	}

	nRoom[xpos][ypos] -= (diffuseDust * cnt);
}

// 2. 공기청정기 로직
void CleanAir() {
	for (int r = 1; r <= R; r++) {
		if (r == 1 || r == R) { // 왼쪽 방향
			for (int c = C-1; c >= 1; c--) {
				nRoom[r][c] = room[r][c + 1];
			}
			if (r == 1) nRoom[r][C] = room[r + 1][C];
			else if (r == R) nRoom[r][C] = room[r - 1][C];
		}
		else if (r == airX[0] || r==airX[1]) { // 오른쪽 방향
			for (int c = 2; c <= C; c++) {
				if (c == 2) nRoom[r][c] = 0;
				else nRoom[r][c] = room[r][c - 1];
			}
		}
		else if (r<airX[0]) { // 공기청정기 위쪽 지역
			nRoom[r][1] = room[r - 1][1];
			nRoom[r][C] = room[r+1][C];
		}
		else if (r > airX[1]) { // 공기청정기 아래쪽 지역
			nRoom[r][1] = room[r + 1][1];
			nRoom[r][C] = room[r - 1][C];
		}
	}
	memcpy(room, nRoom, sizeof(nRoom));
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	scanf("%d %d %d", &R, &C, &T);
	for (int r = 1; r <= R; r++) {
		for (int c = 1; c <= C; c++) {
			scanf("%d", &room[r][c]);
			if (room[r][c] == -1) airX.push_back(r);
		}
	}

	for (int t = 0; t < T; t++) {
		// 1. 미세먼지 확산
		memcpy(nRoom, room, sizeof(room));
		for (int r = 1; r <= R; r++) {
			for (int c = 1; c <= C; c++) {
				if (room[r][c] > 0) DustDiffustion(r, c);
			}
		}
		memcpy(room, nRoom, sizeof(room));

		// 2. 공기청정기
		CleanAir();
	}
	
	// 미세먼지양 계산
	int ans = 0;
	for (int r = 1; r <= R; r++) {
		for (int c = 1; c <= C; c++) {
			if (room[r][c] > 0) ans += room[r][c];
		}
	}
	printf("%d\n", ans);
	return 0;
}