BOJ 15685 : 드래곤 커브 (삼성 SW TEST A형)

삼성 A형 전체 링크

 

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

 

www.acmicpc.net/problem/15685

 

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

 

방향을 먼저 모두 만들고, 시키는 대로 그리면 된다.

 

먼저 움직이기 위한 배열 dy, dx를 선언하자.

 

• 0: x좌표가 증가하는 방향 (→)
• 1: y좌표가 감소하는 방향 (↑)
• 2: x좌표가 감소하는 방향 (←)
• 3: y좌표가 증가하는 방향 (↓)

int dy[] = { 0, -1, 0, 1 };
int dx[] = { 1, 0, -1, 0 };

 

이제 moveList를 만들자.

드래곤 커브의 규칙대로 처음 방향이 3인 경우, moveList는 아래와 같이 만들어진다.

(직접 그려보자)

 

L = 0 : 3

L = 1 : 3 0

L = 2 : 3 0 1 0

L = 3 : 3 0 1 0 1 2 1 0

L = 4 : 3 0 1 0 1 2 1 0 1 2 3 2 1 2 1 0

...

 

규칙은 기존의 배열을 뒤집고, 방향을 + 1 해주면 된다. 방향이 4가 되면 0으로 바꿔주면 된다.

 

L = 2 → [3, 0] → [0, 3] → [1, 4] → [1, 0] = [3, 0, 1, 0] : L = 3

L = 3 → [3, 0, 1, 0] → [0, 1, 0, 3] → [1, 2, 1, 4] → [1, 2, 1, 0] = [3, 0, 1, 0, 1, 2, 1, 0] : L = 4

 

즉, 현재 까지의 배열 → 다음 배열이 2배로 늘어나게 된다.

코드로 구현해보면 아래와 같다.

for (int i = length + 1; i <= length * 2; i++)
	moveList[i - 1] = (moveList[length * 2 - i] + 1) % 4;

 

% 연산자가 헷갈린다면, 하드코딩 하자.

for (int i = length + 1; i <= length * 2; i++)
{
	moveList[i - 1] = (moveList[length * 2 - i] + 1);
	if (moveList[i - 1] == 4) moveList[i - 1] = 0;
}

 

이러한 List를 g 입력에 대해 배열의 길이가 2^g승이 될 때 까지(총 g번) 만들어야 한다.

void DFS(int L, int length)
{
	if (L > g) return;

	for (int i = length + 1; i <= length * 2; i++)
	{
		moveList[i - 1] = (moveList[length * 2 - i] + 1);
		if (moveList[i - 1] == 4) moveList[i - 1] = 0;
	}

	DFS(L + 1, length * 2);
}

 

2의 n승은 비트 연산으로 (1 << n)으로 할 수 있다.

moveList가 완성되었으니, MAP을 이동하면서 드래곤 커브를 표시하자.

int move = 1 << g; /* 2^g */
for (int k = 0; k < move; k++)
{
	y = y + dy[moveList[k]];
	x = x + dx[moveList[k]];

	MAP[y][x] = 1;
}

 

드래곤 커브는 (y, x) 포함 주변이 모두 1이므로, 아래와 같이 계산한다.

int calculate()
{
	int ans = 0;
	for (int y = 0; y < 100; y++) /* map의 크기가 최대 100 */
		for (int x = 0; x < 100; x++)
			if (MAP[y][x] + MAP[y + 1][x] + MAP[y][x + 1] + MAP[y + 1][x + 1] == 4) ans++;
	
	return ans;
}

 

최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX (100 + 20)

int N, x, y, d, g;
int MAP[MAX][MAX];
int moveList[2000];

void DFS(int L, int length)
{
	if (L > g) return;

	for (int i = length + 1; i <= length * 2; i++)
		moveList[i - 1] = (moveList[length * 2 - i] + 1) % 4;

	DFS(L + 1, length * 2);
}

int calculate()
{
	int ans = 0;
	for (int y = 0; y < 100; y++)
		for (int x = 0; x < 100; x++)
			if (MAP[y][x] + MAP[y + 1][x] + MAP[y][x + 1] + MAP[y + 1][x + 1] == 4) ans++;
	
	return ans;
}

int dy[] = { 0, -1, 0, 1 };
int dx[] = { 1, 0, -1, 0 };

int main(void)
{
	scanf("%d", &N);

	for (int i = 0; i < N; i++)
	{
		for (int k = 0; k < 2000; k++) moveList[k] = 0;

		scanf("%d %d %d %d", &x, &y, &d, &g);

		moveList[0] = d;

		DFS(1, 1);

		MAP[y][x] = 1;

		int move = 1 << g; /* 2^g */
		for (int k = 0; k < move; k++)
		{
			y = y + dy[moveList[k]];
			x = x + dx[moveList[k]];

			MAP[y][x] = 1;
		}
	}

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

	return 0;
}

moveList를 초기화 할 때, 1024 까지만 초기화하면 되지만, segment fault 대비로 넉넉하게 잡아두자.