BOJ 17144 : 미세먼지 안녕! (삼성 SW TEST A형)

삼성 A형 전체 링크

 

www.acmicpc.net/workbook/view/1152 (A형 문제집)

 

www.acmicpc.net/problem/17144

 

이후 설명 및 입/출력은 링크 참고

시뮬레이션 문제는 시키는 대로 구현하면 된다.

 

먼저 diffusion 함수를 만들어보자.

 

미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.

• (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
• 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
• 확산되는 양은 Ar,c/5이고 소수점은 버린다.
• (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.

인접한 네 방향으로 확산은 되지만, 공기청정기가 있거나 칸이 없으면, 확산이 일어나지 않는다.

하지만, 같은 먼지끼리는 "확산"이 일어난다.

 

실제 확산이 일어나는지는 아래의 예시를 통해 알 수 있다.

(5, 6)의 10만 봐도, 확산이 일어났기 때문에 10이 줄어들어야 하지만, 그대로 10을 유지하고 있다.

43에서 확산이 일어났기 때문이다.

 

기존의 MAP에 먼지만 동시에 확산이 일어나야 하기 때문에, 아무 것도 없는 tmpMAP을 선언해서,

tmpMAP에 확산이 일어나는 먼지를 저장한 후, 다시 MAP에 더해주면 된다.

/* 순서대로 왼쪽, 위, 오른쪽, 아래 */
int dr[] = { 0,-1,0,1 };
int dc[] = { -1,0,1,0 };

void diffusion()
{
	int tmpA[MAX][MAX];

	for (int r = 1; r <= R; r++)
		for (int c = 1; c <= C; c++)
			tmpA[r][c] = 0;

	for (int r = 1; r <= R; r++)
	{
		for (int c = 1; c <= C; c++)
		{
			if (A[r][c] > 0)
			{
				int cnt, dust;

				cnt = dust = 0;
				for (int i = 0; i < 4; i++)
				{
					int nr, nc;

					nr = r + dr[i];
					nc = c + dc[i];

					if (nr < 1 || nc < 1 || nr > R || nc > C) continue;
					if (A[nr][nc] == -1) continue;

					dust = A[r][c] / 5;

					tmpA[nr][nc] += dust;
					cnt++;
				}

				A[r][c] -= dust * cnt;
			}
		}
	}

	for (int r = 1; r <= R; r++)
		for (int c = 1; c <= C; c++)
			if (tmpA[r][c]) A[r][c] += tmpA[r][c];
}

 

확산이 일어났으므로, 이제 공기청정기를 통해 먼지를 움직여보자.

(1, 1) ~ (공기청정기 위의 R 좌표, C)는 반시계로 이동하고, 

(공기청정기 아래의 R 좌표, 1) ~ (R, C)는 시계로 이동하게 하면 된다.

 

공기청정기 쪽 방향부터 하면 따로 맵을 저장시킬 필요가 없다.

마지막으로 이동하는 먼지는 0으로 덮는 것을 잊지말자.

 

move 코드는 최종 코드를 참고하자.

#include <stdio.h>

#define MAX (50 + 10)

int R, C, T;
int A[MAX][MAX];

typedef struct st
{
	int r;
	int c;
}RC;

RC cleaner[2];
int ccnt;

void input()
{
	scanf("%d %d %d", &R, &C, &T);

	for (int r = 1; r <= R; r++)
	{
		for (int c = 1; c <= C; c++)
		{
			scanf("%d", &A[r][c]);

			if (A[r][c] == -1)
			{
				cleaner[ccnt].r = r;
				cleaner[ccnt++].c = c;
			}
		}
	}
}

void output()
{
	for (int r = 1; r <= R; r++)
	{
		for (int c = 1; c <= C; c++)
			printf("%d ", A[r][c]);
		putchar('\n');
	}
}

/* 순서대로 왼쪽, 위, 오른쪽, 아래 */
int dr[] = { 0,-1,0,1 };
int dc[] = { -1,0,1,0 };

void diffusion()
{
	int tmpA[MAX][MAX];

	for (int r = 1; r <= R; r++)
		for (int c = 1; c <= C; c++)
			tmpA[r][c] = 0;

	for (int r = 1; r <= R; r++)
	{
		for (int c = 1; c <= C; c++)
		{
			if (A[r][c] > 0)
			{
				int cnt, dust;

				cnt = dust = 0;
				for (int i = 0; i < 4; i++)
				{
					int nr, nc;

					nr = r + dr[i];
					nc = c + dc[i];

					if (nr < 1 || nc < 1 || nr > R || nc > C) continue;
					if (A[nr][nc] == -1) continue;

					dust = A[r][c] / 5;

					tmpA[nr][nc] += dust;
					cnt++;
				}

				A[r][c] -= dust * cnt;
			}
		}
	}

	for (int r = 1; r <= R; r++)
		for (int c = 1; c <= C; c++)
			if (tmpA[r][c]) A[r][c] += tmpA[r][c];
}

void move()
{
	int up_r = cleaner[0].r;
	int down_r = cleaner[1].r;
	
	/* (1, 1) ~ (up_r , C)의 반시계 */
	for (int r = up_r - 1; r > 1; r--) A[r][1] = A[r - 1][1];
	for (int c = 1; c <= C - 1; c++) A[1][c] = A[1][c + 1];
	for (int r = 1; r <= up_r - 1; r++) A[r][C] = A[r + 1][C];
	for (int c = C; c > 1; c--) A[up_r][c] = A[up_r][c - 1];
	
	A[up_r][2] = 0;

	/* (down_r, 1) ~ (R, C)의 시계 */
	for (int r = down_r + 1; r <= R - 1; r++) A[r][1] = A[r + 1][1];
	for (int c = 1; c <= C - 1; c++) A[R][c] = A[R][c + 1];
	for (int r = R; r > down_r; r--) A[r][C] = A[r - 1][C];
	for (int c = C; c > 1; c--) A[down_r][c] = A[down_r][c - 1];
	
	A[down_r][2] = 0;
}

int main(void)
{
	input();

	for (int time = 0; time < T; time++)
	{
		diffusion();
		move();
	}

	int count = 0;
	for (int r = 1; r <= R; r++)
		for (int c = 1; c <= C; c++)
			if (A[r][c] != -1) count += A[r][c];

	printf("%d\n", count);

	return 0;
}