BOJ 15685 드래곤 커브

사용한 알고리즘

시뮬레이션

알고리즘 설명

드래곤 커프의 n-1번째 커브와 n번째 커브와의 관계는 데칼코마니와 같다.
커프를 좌표가 아닌 커프가 진행하는 방향인 0(0도), 1(90도), 2(180도), 3(270도)으로 표현하자.
이 뒤에 커브가 증가하는 형태는 Arr[N, N/2+1] = Arr[1,N/2] + 1 mod 4와 같은 점화식으로 표현할 수 있다.
위 점화식으로 g번째 커프의 배열을 만든 뒤에 시뮬레이션을 진행한다.
시뮬레이션 뒤에 만들어지는 1x1 정사각형 개수를 센다.

풀이

// baekjoon 15685 yechan
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_N=101;
const int SIZE=1<<12;
const int dir[4][2] = { {1, 0}, {0, -1}, {-1, 0}, {0, 1} };

int N, arr[SIZE], x, y, d, g;
bool visited[MAX_N][MAX_N];

// 정사각형 개수 카운트
int getCntRect() {
	int ret = 0;
	for (int i=0; i<MAX_N-1; i++)
		for (int j=0; j<MAX_N-1; j++)
			if (visited[i][j] && visited[i+1][j] && visited[i][j+1] && visited[i+1][j+1])
				ret++;
	return ret;
}

// 시뮬레이션 진행
void draw(int x, int y, int g) {
	int idx = 0;
	int maxIdx = 1<<g;
	visited[x][y] = true;

	while (idx < maxIdx) {
		x = x + dir[arr[idx]][0];
		y = y + dir[arr[idx]][1];
		if (0 <= x && x < MAX_N && 0 <= y && y < MAX_N) visited[x][y] = true;
		idx++;
	}
}

// 데칼코마니 형태로 Arr를 생성하기 cnt-1 번째 배열로 cnt 번째 배열 생성하기
void genArr(int cnt, int maxCnt) {
	if (cnt > maxCnt) return;

	for (int i=(1<<cnt)-1, j=0; i>=(1<<(cnt-1)); i--, j++) {
		arr[i] = (arr[j]+1)%4;
	}
	genArr(cnt+1, maxCnt);
}



int main() {
	scanf("%d",&N);
	for (int i=0; i<N; i++) {
		scanf("%d%d%d%d", &x, &y, &d, &g);
		arr[0]=d;
		genArr(1,g);
		draw(x, y, g);
	}
	printf("%d\n", getCntRect());
	return 0;
}