BOJ 15685 - 드래곤 커브

링크: https://www.acmicpc.net/problem/15685

문제

알고스팟의 JM북에 그려진 그 드래곤 커브가 맞다. 

간단한 수학 규칙으로 그려지는 그림인데, 이 문제에서는 드래곤 커브가 네 꼭지점을 모두 지나는 칸이 몇 개인지 구하는 거였다.

풀이

드래곤 커브의 규칙을 미리 만들어놓고, 드래곤 커브의 시작점과 시작 방향이 주어졌을 때 규칙에 맞게 이동하면서 주변 칸에 해당 꼭지점이 지나갔음을 기록한다.

드래곤 커브는 이전 세대의 드래곤 커브를 이용하기 때문에 반복적인 구조이다. 각 방향과 관련된 변수들을 잘 설정하면 쉽게 구현할 수 있다. 나는 문제에 맞춰 우,상,좌,하 순서로 0,1,2,3을 사용했다.

원소들은 진행 방향, 드래곤 커브를 $G_0 = \{\dots, a, b, c, d\}$ 이라 하자. 이 커브를 전체 90도 회전하는 것은 각 원소들을 모두 90도 회전한 것과 같다. 즉, $G_0$을 90도 회전한 수열 $G_0' = \{\dots, a', b', c', d'\}$ 이다.

이전 세대를 수열 $G_0$라고 하면 다음 세대의 드래곤 커브는 $G_1 = G_0' + G_0$ 로 전개된다.

0세대부터 10세대까지 미리 구하는 코드는 굉장히 단순하다.

	int dx[] = { 1, 0, -1, 0 };
	int dy[] = { 0, -1, 0, 1 };
	vector<int> dragon(1, 0);
	for (int i = 0; i <= 10; ++i) {
	for (int j = (int)dragon.size() - 1; j >= 0; --j)
	dragon.push_back((dragon[j] + 1) % 4);
	}

view raw generate-dragon-curve.cpp hosted with ❤ by GitHub

드래곤 커브는 선분, 우리가 확인해야 하는 것은 칸이기 때문에 드래곤 커브가 어떤 점 $(y, x)$를 지날 때마다, 주변 4칸에 잘 기록하면 된다.

코드

	#include <bits/stdc++.h>
	using namespace std;
	static int dx[] = { 1, 0, -1, 0 };
	static int dy[] = { 0, -1, 0, 1 };
	int grid[111][111];
	void paint(int x, int y) {
	for (int d = 0; d < 4; ++d) {
	grid[y + (d / 2)][x + (d % 2)] |= 1 << d;
	}
	}
	bool isPainted(int x, int y) {
	return grid[y][x] == 15;
	}
	int main() {
	vector<int> dragon(1, 0);
	for (int i = 0; i <= 10; ++i) {
	for (int j = (int)dragon.size() - 1; j >= 0; --j)
	dragon.push_back((dragon[j] + 1) % 4);
	}
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
	int x, y, d, g;
	scanf("%d %d %d %d", &x, &y, &d, &g);
	int gen_size = 1 << g;
	for (int i = 0; i <= gen_size; ++i) {
	paint(x, y);
	if (i == gen_size) break;
	int nd = (dragon[i] + d) % 4;
	x += dx[nd];
	y += dy[nd];
	}
	}
	int ans = 0;
	for (int i = 0; i < 105; ++i)
	for (int j = 0; j < 105; ++j)
	ans += isPainted(j, i);
	printf("%d\n", ans);
	return 0;
	}

view raw boj-15685.cpp hosted with ❤ by GitHub