[코드트리] 드래곤 커브 (삼성 SW 역량테스트 2018 상반기 오후 1번)

 

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

 

삼성 A형 전체 링크

 

https://www.codetree.ai/training-field/frequent-problems/problems/dragon-curve

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

 

드래곤 커브 문제 풀이는 BOJ 15685 : 드래곤 커브와 같다. (x, y 좌표가 반대)

#include <stdio.h>

#define MAX (100 + 20)

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

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

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[x][y] + MAP[x + 1][y] + MAP[x][y + 1] + MAP[x + 1][y + 1] == 4) ans++;

	return ans;
}

int main(void)
{
	// scanf("%d", &T);
	T = 1;
	for (int tc = 1; tc <= T; tc++)
	{
		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[x][y] = 1;

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

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

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

	return 0;
}