SWEA 2382 : 미생물 격리 (모의 SW 역량테스트)

 

A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기)

 

삼성 A형 전체 링크

 

모의 SW 역량테스트 문제집

 

미생물 격리 링크

 

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

미생물의 구조체 BIO에는 미생물의 방향, 개수, 그리고 시뮬레이션을 위해 max값을 저장하도록 만든다.

아래의 조건을 보자.

 

   ④ 이동 후 두 개 이상의 군집이 한 셀에 모이는 경우 군집들이 합쳐지게 된다. 
       합쳐 진 군집의 미생물 수는 군집들의 미생물 수의 합이며,

      이동 방향은 군집들 중 미생물 수가 가장 많은 군집의 이동방향이 된다. 
       합쳐지는 군집의 미생물 수가 같은 경우는 주어지지 않으므로 고려하지 않아도 된다.

 

합쳐진 군집이 아닌, 각 군집의 미생물 수가 가장 큰 군집의 방향으로 갱신되므로, max를 저장해서 비교해야 한다.

 

그리고 현재 미생물의 상태의 정보인 MAP과 다음 상태의 정보를 저장할 nextMAP을 선언한다.

방향은 dr, dc 배열을 이용해 문제에서 정의한 대로 선언한다.

changeDir을 이용해 약품에 미생물이 도착한 경우 방향을 변경할 수 있도록 한다.

changeDir[1] = 2, changeDir[2] = 1, changeDir[3] = 4, changeDir[4] = 3이 되도록 정의하면, 

상/하, 좌/우를 쉽게 변경할 수 있다.

#define MAX (100 + 50)

int T, N, M, K;

typedef struct st
{
	int dir;
	int num;
	int maxNum;
}BIO;

BIO MAP[MAX][MAX];
BIO nextMAP[MAX][MAX];

/* 1: 상, 2: 하, 3: 좌, 4: 우 */
int dr[] = { 0, -1, 1, 0, 0 };
int dc[] = { 0, 0, 0, -1, 1 };
int changeDir[5] = { 0, 2, 1, 4, 3 };

void input()
{
	scanf("%d %d %d", &N, &M, &K);

	BIO init = { 0 };
	for (int r = 0; r < N; r++)
		for (int c = 0; c < N; c++)
			MAP[r][c] = init;

	for (int i = 0; i < K; i++)
	{
		int r, c, num, dir;

		scanf("%d %d %d %d", &r, &c, &num, &dir);

		MAP[r][c].num = num;
		MAP[r][c].maxNum = num;
		MAP[r][c].dir = dir;
	}
}

---

시뮬레이션을 다음과 같은 순서대로 M번 진행한다.

 

1) MAP[r][c]의 num이 0이면 미생물이 없으므로 continue한다.

2) MAP[r][c]의 다음 좌표 (nr, nc)가 약품이 칠해진 경우, 미생물의 수를 감소하고 방향을 변경한다.

 

3-1) (nr, nc)가 빈 공간이라면 이동, nextMAP에 이동한다.

3-2) (nr, nc)에 미생물이 이미 존재하고, (nr, nc)의 미생물이 더 크다면 수를 증가시킨다.

3-3) (nr, nc)에 미생물이 이미 존재하고, 자신이 더 크다면, nextMAP을 갱신한다. (max 변경, 방향 전환, num 추가)

 

4) nextMAP에 이동한 미생물을 다시 MAP으로 옮기고, nextMAP을 초기화한다. 

   이때, MAP[r][c]의 maxNum은 다시 num으로 초기화한다.

 

5) M번 진행 후, 미생물을 모두 더한다.

 

위 시뮬레이션 과정에 대해 main에 주석을 추가하였으므로, 전체 코드를 참고하자.

#include <stdio.h>

#define MAX (100 + 50)

int T, N, M, K;

typedef struct st
{
	int dir;
	int num;
	int maxNum;
}BIO;

BIO MAP[MAX][MAX];
BIO nextMAP[MAX][MAX];

/* 1: 상, 2: 하, 3: 좌, 4: 우 */
int dr[] = { 0, -1, 1, 0, 0 };
int dc[] = { 0, 0, 0, -1, 1 };
int changeDir[5] = { 0, 2, 1, 4, 3 };

void input()
{
	scanf("%d %d %d", &N, &M, &K);

	BIO init = { 0 };
	for (int r = 0; r < N; r++)
		for (int c = 0; c < N; c++)
			MAP[r][c] = init;

	for (int i = 0; i < K; i++)
	{
		int r, c, num, dir;

		scanf("%d %d %d %d", &r, &c, &num, &dir);

		MAP[r][c].num = num;
		MAP[r][c].maxNum = num;
		MAP[r][c].dir = dir;
	}
}

int main(void)
{
	scanf("%d", &T);
	for (int tc = 1; tc <= T; tc++)
	{
		input();

		for (int m = 0; m < M; m++)
		{
			for (int r = 0; r < N; r++)
			{
				for (int c = 0; c < N; c++)
				{
					/* 1) 미생물이 없으면 continue */
					if (MAP[r][c].num == 0) continue;

					int currentNum = MAP[r][c].num;

					int nr, nc;

					nr = r + dr[MAP[r][c].dir];
					nc = c + dc[MAP[r][c].dir];

					/* 2) 약품이 칠해진 구역, 미생물 수 감소 및 방향 변경 */
					if (nr == 0 || nr == N - 1 || nc == 0 || nc == N - 1)
					{
						MAP[r][c].num /= 2;
						MAP[r][c].dir = changeDir[MAP[r][c].dir];
					}

					/* 3-1) 빈 공간이라면 이동 */
					if (nextMAP[nr][nc].num == 0) nextMAP[nr][nc] = MAP[r][c];

					/* 3-2) 이동하려는 장소의 maxNum이 더 큰 경우 미생물의 수만 증가 */
					else if (nextMAP[nr][nc].maxNum > currentNum) nextMAP[nr][nc].num += MAP[r][c].num;
					else /* 3-3) 자신이 더 큰 경우, max 변경 및 방향 전환, 미생물 추가 */
					{
						nextMAP[nr][nc].maxNum = currentNum;
						nextMAP[nr][nc].dir = MAP[r][c].dir;
						nextMAP[nr][nc].num += MAP[r][c].num;
					}
				}
			}

			/* 4) move 종료, nextMAP을 MAP에 copy하고 초기화 */
			BIO init = { 0 };
			for (int r = 0; r < N; r++)
			{
				for (int c = 0; c < N; c++)
				{
					MAP[r][c] = nextMAP[r][c];
					MAP[r][c].maxNum = MAP[r][c].num;
					nextMAP[r][c] = init;
				}
			}
		}

		/* 5) 남은 미생물을 모두 더한다. */
		int sum = 0;
		for (int r = 0; r < N; r++)
			for (int c = 0; c < N; c++)
				sum += MAP[r][c].num;

		printf("#%d %d\n", tc, sum);
	}

	return 0;
}