BOJ 21610 : 마법사 상어와 비바라기 (삼성 SW TEST A형)

 

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

 

삼성 A형 전체 링크

 

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

 

www.acmicpc.net/problem/21610

 

 

구름의 좌표를 저장할 RC 구조체가 필요하다.

최초 구름 4칸을 입력하고, cloud count = ccnt를 4로 설정해두자.

그리고 MAP의 좌표는 (1, 1)부터 받는다.

#define MAX (50 + 5)

int N, M;
int MAP[MAX][MAX];

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

RC cloud[MAX * MAX] = { 0 };
int ccnt;

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

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			scanf("%d", &MAP[r][c]);

	cloud[0].r = N; cloud[0].c = 1;
	cloud[1].r = N; cloud[1].c = 2;
	cloud[2].r = N - 1; cloud[2].c = 1;
	cloud[3].r = N - 1; cloud[3].c = 2;
	ccnt = 4;
}

---

방향에 대한 변수 d와 몇 칸을 움직일지에 대한 변수 s를 입력받으면서 시뮬레이션을 진행한다.

구름을 움직이고, 물을 추가하고, 물복사버그 마법을 사용하고, 구름을 다시 생성한다.

for (int i = 0; i < M; i++)
{
	int d, s;

	scanf("%d %d", &d, &s);

	moveCloud(d, s);
	addWater();
	copyWater();
	makeCloud();
}

---

문제에서 제시한 8방향에 대한 배열을 dr, dc로 선언한다.

방향은 1부터 주어지므로, 배열의 가장 처음은 0으로 만들었다.

그리고 cloud 배열을 순회하면서 좌표를 s번 변경한다.

/* 0, ←, ↖, ↑, ↗, →, ↘, ↓, ↙  */
int dr[] = { 0, 0, -1, -1, -1, 0, 1, 1, 1 };
int dc[] = { 0, -1, -1, 0, 1, 1, 1, 0, -1 };

void moveCloud(int dir, int size)
{
	for (int i = 0; i < ccnt; i++)
	{
		for (int s = 0; s < size; s++)
		{
			int nr, nc;

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

			if (nr == N + 1) nr = 1;
			if (nr == 0) nr = N;
			if (nc == N + 1) nc = 1;
			if (nc == 0) nc = N;

			cloud[i].r = nr;
			cloud[i].c = nc;
		}
	}
}

첫 행과 끝 행, 첫 열과 끝 열이 연결되어 있기 때문에, if문으로 N + 1이나 0이 되는 경우 좌표를 변경한다.

 

addWater는 현재 구름의 배열의 좌표를 이용하여 MAP을 1씩 증가시키면 된다.

void addWater()
{
	for (int i = 0; i < ccnt; i++)
		MAP[cloud[i].r][cloud[i].c]++;
}

---

copyWater는 구름을 기준으로 4방향 대각선 좌표를 보고 물을 증가시킨다.

따라서 drr, dcc 배열을 따로 선언하였다.

/* ↖, ↗, ↘, ↙ */
int drr[] = { -1, -1, 1, 1 };
int dcc[] = { -1, 1, 1, -1 };
void copyWater()
{
	for (int i = 0; i < ccnt; i++)
	{
		int countCloud = 0;
		for (int dir = 0; dir < 4; dir++)
		{
			int nr, nc;

			nr = cloud[i].r + drr[dir];
			nc = cloud[i].c + dcc[dir];

			countCloud += !!MAP[nr][nc];
		}

		MAP[cloud[i].r][cloud[i].c] += countCloud;
	}
}

!!MAP[nr][nc]를 하면 MAP이 0보다 큰 경우는 1로, 0인 경우는 0이 된다.

---

마지막으로 MAP의 모든 좌표를 돌면서 2보다 큰 값을 찾는다.

이 때, checkCloud 함수를 이용하여 현재 구름의 좌표인 경우는 무시한다.

그리고 구름인 칸의 물의 양이 2씩 줄어든다고 하였으므로 MAP을 감소한다.

새로운 구름은 newCloud에 담고, 최종적으로 다시 cloud에 복사한다.

void makeCloud()
{
	RC newCloud[MAX * MAX] = { 0 };
	int ncnt = 0;

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (MAP[r][c] < 2) continue;

			/* 현재 구름인지 확인 */
			if (checkCloud(r, c)) continue;

			MAP[r][c] -= 2;

			newCloud[ncnt].r = r;
			newCloud[ncnt++].c = c;
		}
	}

	for (int i = 0; i < ncnt; i++)
		cloud[i] = newCloud[i];

	ccnt = ncnt;
}

 

현재 구름의 좌표는 cloud 배열을 모두 체크하면서 같은 좌표가 있는지 확인하면 된다.

int checkCloud(int r, int c)
{
	for (int i = 0; i < ccnt; i++)
		if (cloud[i].r == r && cloud[i].c == c) return 1;

	return 0;
}

 

최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX (50 + 5)

int N, M;
int MAP[MAX][MAX];

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

RC cloud[MAX * MAX] = { 0 };
int ccnt;

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

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			scanf("%d", &MAP[r][c]);

	cloud[0].r = N; cloud[0].c = 1;
	cloud[1].r = N; cloud[1].c = 2;
	cloud[2].r = N - 1; cloud[2].c = 1;
	cloud[3].r = N - 1; cloud[3].c = 2;
	ccnt = 4;
}

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

/* 0, ←, ↖, ↑, ↗, →, ↘, ↓, ↙  */
int dr[] = { 0, 0, -1, -1, -1, 0, 1, 1, 1 };
int dc[] = { 0, -1, -1, 0, 1, 1, 1, 0, -1 };

void moveCloud(int dir, int size)
{
	for (int i = 0; i < ccnt; i++)
	{
		for (int s = 0; s < size; s++)
		{
			int nr, nc;

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

			if (nr == N + 1) nr = 1;
			if (nr == 0) nr = N;
			if (nc == N + 1) nc = 1;
			if (nc == 0) nc = N;

			cloud[i].r = nr;
			cloud[i].c = nc;
		}
	}
}

void addWater()
{
	for (int i = 0; i < ccnt; i++)
		MAP[cloud[i].r][cloud[i].c]++;
}

/* ↖, ↗, ↘, ↙ */
int drr[] = { -1, -1, 1, 1 };
int dcc[] = { -1, 1, 1, -1 };
void copyWater()
{
	for (int i = 0; i < ccnt; i++)
	{
		int countCloud = 0;
		for (int dir = 0; dir < 4; dir++)
		{
			int nr, nc;

			nr = cloud[i].r + drr[dir];
			nc = cloud[i].c + dcc[dir];

			countCloud += !!MAP[nr][nc];
		}

		MAP[cloud[i].r][cloud[i].c] += countCloud;
	}
}

int checkCloud(int r, int c)
{
	for (int i = 0; i < ccnt; i++)
		if (cloud[i].r == r && cloud[i].c == c) return 1;

	return 0;
}

void makeCloud()
{
	RC newCloud[MAX * MAX] = { 0 };
	int ncnt = 0;

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (MAP[r][c] < 2) continue;

			/* 현재 구름인지 확인 */
			if (checkCloud(r, c)) continue;

			MAP[r][c] -= 2;

			newCloud[ncnt].r = r;
			newCloud[ncnt++].c = c;
		}
	}

	for (int i = 0; i < ncnt; i++)
		cloud[i] = newCloud[i];

	ccnt = ncnt;
}

int main()
{
	input();

	for (int i = 0; i < M; i++)
	{
		int d, s;

		scanf("%d %d", &d, &s);

		moveCloud(d, s);
		addWater();
		copyWater();
		makeCloud();
	}

	int sum = 0;
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			sum += MAP[r][c];

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

	return 0;
}

 

실제 A형의 경우 tc가 여러개이다. 이 때, MAP을 모두 초기화하는 것이 좋다.

tc가 1개인 경우라서 MAP 주변이 0으로 선언되지만,

tc가 여러 개인 경우에 MAP의 크기가 줄어들면 MAP 주변의 값이 0이 아니게 된다.