[백준] 17144번 - 미세먼지 안녕! / C++

문제

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R × C인 격자판으로 나타냈고, 1 × 1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.

공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.

1초 동안 아래 적힌 일이 순서대로 일어난다.

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

다음은 확산의 예시이다.

왼쪽과 오른쪽에 칸이 없기 때문에, 두 방향으로만 확산이 일어났다.

인접한 네 방향으로 모두 확산이 일어난다.

공기청정기가 있는 칸으로는 확산이 일어나지 않는다.

공기청정기의 바람은 다음과 같은 방향으로 순환한다.

방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.

 

입력

첫째 줄에 R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000)가 주어진다.

둘째 줄부터 R개의 줄에 Ar,c (-1 ≤ Ar,c ≤ 1,000)가 주어진다. 공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양이다. -1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸 이상 떨어져 있다.

 

출력

첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.

 

코드

#include <iostream>
#include <cstring>

using namespace std;

int R;
int C;
int T;
int A[51][51];	// 미세먼지 양
int ap[2];	// 공기청정기가 위치한 행

void spread_dust()
{
	int i, j, k;
	int dr, dc, cnt;		// cnt는 확산된 칸의 개수를 저장
	int S[51][51];			// 주변 칸으로부터 확산되어 온 미세먼지 양을 저장
	int d[] = {-1, 1, 0, 0};	// 상, 하, 좌, 우로 확산하기 위해 사용

	memset(S, 0, sizeof(S));	// 모든 칸을 0으로 초기화
	for (i = 1; i <= R; i++)
	{
		for (j = 1; j <= C; j++)
		{
			// 공기청정기가 있는 경우 패스
			if (A[i][j] == -1)
				continue;
			// 확산된 칸의 개수 초기화
			cnt = 0;
			for (k = 0; k < 4; k++)
			{
				// 현재 칸을 기준으로 상하좌우에 위치한 칸에 대하여
				dr = i + d[k];
				dc = j + d[3 - k];
				// 공기청정기가 있는 경우 패스
				if (A[dr][dc] == -1)
					continue;
				// R X C의 범위 내에 해당하는 경우 확산
				if (dr > 0 && dr <= R && dc > 0 && dc <= C)
				{
					S[dr][dc] += A[i][j] / 5;
					cnt++;
				}
			}
			// 확산 후 현재 칸의 미세먼지 양을 조절
			A[i][j] = A[i][j] - A[i][j] / 5 * cnt;
		}
	}
	// 모든 칸에 대하여 남은 미세먼지 양에 주변으로부터 확산된 미세먼지 양을 더함
	for (i = 1; i <= R; i++)
	{
		for (j = 1; j <= C; j++)
		{
			A[i][j] += S[i][j];
		}
	}
}

void run_top()
{
	int i, j;

	// 시계방향으로 돌며 한 칸씩 값을 이동함
	for (i = ap[0] - 1; i > 1; i--)
	{
		A[i][1] = A[i - 1][1];
	}
	for (j = 1; j < C; j++)
	{
		A[1][j] = A[1][j + 1];
	}
	for (i = 1; i < ap[0]; i++)
	{
		A[i][C] = A[i + 1][C];
	}
	for (j = C; j > 2; j--)
	{
		A[ap[0]][j] = A[ap[0]][j - 1];
	}
	// 공기청정기의 바람이 시작하는 칸의 미세먼지 양을 0으로 설정
	A[ap[0]][2] = 0;
}

void run_bottom()
{
	int i, j;

	// 반시계방향으로 돌며 한 칸씩 값을 이동함
	for (i = ap[1] + 1; i < R; i++)
	{
		A[i][1] = A[i + 1][1];
	}
	for (j = 1; j < C; j++)
	{
		A[R][j] = A[R][j + 1];
	}
	for (i = R; i > ap[1]; i--)
	{
		A[i][C] = A[i - 1][C];
	}
	for (j = C; j > 2; j--)
	{
		A[ap[1]][j] = A[ap[1]][j - 1];
	}
	// 공기청정기의 바람이 시작하는 칸의 미세먼지 양을 0으로 설정
	A[ap[1]][2] = 0;
}

int main()
{
	int i, j, t = 0;
	int answer = 0;

	cin >> R >> C >> T;
	for (i = 1; i <= R; i++)
	{
		for (j = 1; j <= C; j++)
		{
			cin >> A[i][j];
			if (A[i][j] == -1)
				ap[t++] = i;
		}
	}
	for (t = 0; t < T; t++)
	{
		spread_dust();
		run_top();
		run_bottom();
	}
	for (i = 1; i <= R; i++)
	{
		for (j = 1; j <= C; j++)
		{
			if (A[i][j] != -1)
				answer += A[i][j];
		}
	}
	cout << answer << endl;
	return 0;
}

 

링크

17144번: 미세먼지 안녕!

inbdni/Baekjoon