[BOJ][삼성기출] 15685. 드래곤 커브

문제

드래곤 커브

문제 접근

DFS를 활용한 시뮬레이션 문제이다.

관건1. 드래콘 커브의 규칙 찾기

드래곤 커브를 그릴 때마다 그린 방향을 누적시킨다.
K세대 드래곤 커브는 K-1세대 드래곤 커브가 그려지며 누적된 방향을 거꾸로 순회하며 반시계 방향으로 90도 회전시킨 방향으로 한 획씩 그어가며 그려진다.

따라서 K세대 드래곤 커브를 그리기 위해서는 K-1세대 드래곤 커브가 그려질 동안 사용된 방향 정보가 필요하다. 이를 vector< int > Dir 를 선언하여 구현했다. (각 드래곤 커브를 그리기 전 초기화를 해줘야 한다.)

dfs 함수 내에서는 인자로 받은 방향 벡터를 통해 드래곤 커브를 그린 후, 다음 드래곤 커브를 그릴 방향 벡터(vector< int > Next)를 채워나간다.
여기서 Next는 현재까지 누적된 방향(Dir)을 뒤쪽부터 순회하며 next_dir 함수를 통해 얻은 다음 방향을 차례로 원소로 입력받는다.

이렇게 구현할 경우 벡터의 크기는 2배씩 늘어난다. (1->2->4-> ...)
이 규칙을 위해 0세대 커브는 dfs에 포함시키지 않았다. 하지만 0세대 커브의 방향은 K세대 드래곤 커브의 방향을 구하는 데 사용되므로 Dir 벡터에 우선 넣어두고, 1세대 드래곤 커브를 그릴 때만 dfs 함수 내에서 예외처리를 해주는 방식으로 처리하였다.

관건2. 좌표 입력받기

일반적인 좌표 평면과 다르니 주의해야 한다.

관건3. 사각형 구하기

크기가 1x1인 정사각형의 네 꼭지점이 모두 드래곤 커브에 속할 경우 개수에 포함된다.
드래곤 커브가 방문한 곳을 1로 설정했으며, map을 돌며 네 꼭지점이 모두 1인 정사각형 개수를 셌다.

풀이

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

int N, D, G, X, Y, rst;
int dy[] = { 0, -1, 0, 1 };
int dx[] = { 1, 0, -1, 0 };
int map[101][101];
vector<int> Dir;

int next_dir(int dir) {
	return ++dir > 3 ? 0 : dir;
}

int is_range(int x, int y) {
	if (x >= 0 && x <= 100 && y >= 0 && y <= 100) return true;
	return false;
}

void calculate() {
	int dx[] = { 0, 1, 0 };
	int dy[] = { 1, 0, -1 };

	for (int i = 0; i <= 99; i++) { // 100 x 100 개의 격자에 대해서 조사
		for (int j = 0; j <= 99; j++) {
			bool flag = true;
			if (!map[i][j]) flag = false;
			int nx = i, ny = j;
			for (int d = 0; d < 3; d++) {
				nx += dx[d];
				ny += dy[d];
				if (!map[nx][ny]) flag = false;
			}
			if (flag) rst++;
		}
	}
}

void dfs(vector<int> Prev, int g) { // draw curve
	if (g > G) {
		return;
	}
	vector<int> Next;
	if (g == 1) {
		int dir = Prev[1];
		X += dx[dir];
		Y += dy[dir];
		if (is_range(X, Y)) map[Y][X] = 1;
	}
	else {
		for (int i = 0; i < Prev.size(); i++) {
			int dir = Prev[i];
			X += dx[dir];
			Y += dy[dir];
			Dir.push_back(dir);
			if (is_range(X, Y)) map[Y][X] = 1;	
		}
	}

	// get next dir vector
	for (int i = Dir.size() - 1; i >= 0; i--) {
		Next.push_back(next_dir(Dir[i]));
	}
	dfs(Next, g + 1);
}

void draw_curve() {
	map[Y][X] = 1;
	X += dx[D];
	Y += dy[D];
	
	Dir.push_back(D);
	Dir.push_back(next_dir(D));
	if (is_range(X, Y)) {
		map[Y][X] = 1;
	}
	dfs(Dir, 1); // 1세대부터 시작
}

int main() {
	cin >> N;
	memset(map, 0, sizeof(map));
	for (int i = 0; i < N; i++) {
		cin >> X >> Y >> D >> G;
		Dir.clear();
		draw_curve();
	}
	calculate();
	cout << rst << endl;
}