[C++] 백준 15685번 드래곤 커브

시뮬레이션 문제입니다.

N개의 드래곤 커브가 (x,y)좌표에서 D방향으로 G레벨로 있을 때
네 꼭짓점이 드래곤 커브의 일부인 1x1 크기의 정사각형의 개수를 구하는 문제입니다.

다음의 규칙들을 이용해서 문제를 해결했습니다.

드래곤 커브의 N레벨은
드래곤 커브의 N-1레벨과 드래곤 커브의 N-1레벨의 모양을 90도를 한 것을 끝에 붙인 모양입니다.
고로 드래곤 커브는 2^n개의 선분을 가지게 됩니다.

드래곤 커브는 시작지점은 다르지만 결국 패턴은 방향에 따른 4가지 밖에 없습니다.
그래서 4가지 패턴에 대해서 전부 배열에 넣어두고
각 레벨에 따라서 패턴의 횟수를 실행시켜줬습니다.

이렇게 실행시키면서 체크된 (x, y)좌표는 체크를 해두고
모든 실행이 끝났을 때 정사각형인지 체크를 하면 됩니다.

 

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
using namespace std;

bool map[110][110];
int pattern[4][2049];
int quo[11] = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024 };

int change(int num)
{
	switch (num) {
	case 0:
		num = 1;
		break;
	case 1:
		num = 2;
		break;
	case 2:
		num = 3;
		break;
	case 3:
		num = 0;
		break;
	}
	return num;
}

void SetPattern()
{
	pattern[0][0] = 0; //우
	pattern[1][0] = 1; //상
	pattern[2][0] = 2; //좌
	pattern[3][0] = 3; //하

	for (int i = 0; i < 4; ++i) {
		for (int j = 0; j < 11; ++j) {
			for (int k = 0; k < quo[j]; ++k) {
				pattern[i][quo[j] + k] = change(pattern[i][quo[j] - k - 1]);
			}
		}
	}
}

void run(int x, int y, int d, int g)
{
	map[y][x] = true;
	for (int i = 0; i < quo[g]; ++i) {
		switch (pattern[d][i]) {
		case 0:
			++x;
			break;
		case 1:
			--y;
			break;
		case 2:
			--x;
			break;
		case 3:
			++y;
			break;
		}
		map[y][x] = true;
	}
}

void find()
{
	int count = 0;

	for (int i = 0; i < 101; ++i) {
		for (int j = 0; j < 101; ++j) {
			if (map[i][j] & map[i + 1][j] & map[i][j + 1] & map[i + 1][j + 1]) {
				++count;
			}
		}
	}

	cout << count << endl;
}

int main(int argc, char* argv[])
{
	memset(map, false, sizeof(map));
	SetPattern();

	int n;
	int x, y, d, g;

	cin >> n;

	for (int i = 0; i < n; ++i) {
		cin >> x >> y >> d >> g;

		run(x, y, d, g);
	}

	find();

	return 0;
}