[BOJ15685] 드래곤커브

[BOJ15685] 드래곤커브

---

문제 링크

---

문제 설명

• 드래곤 커브는 시작 점, 시작 방향, 세대의 세가지 속성 으로 이루어져있다.
• 다음 그림은 시작 점이 (0,0)이고 방향이 오른쪽인 0세대이고 길이가 1인 드래곤 커브이다(0세대 드래곤 커브는 길이가 1인 선분이다)(그림 출처 : 백준 온라인 저지).

---

---

• 1세대 드래곤 커브는 0세대 드래곤 커브 끝 점을 기준으로 0세대 드래곤 커브를 시계 방향으로 90도 회전시켜 추가 한다 (그림 출처 : 백준 온라인 저지).

---

---

• 마찬가지로 2세대, 3세대 드래곤커브 역시 전 세대 드래곤 커브 끝 점을 기준으로 시계 방향으로 90도 회전시켜 추가 한다(그림 출처 : 백준 온라인 저지).

---

---

• 입력으로는 드래곤 커브 개수, 그리고 그 개수에 맞춰 x,y(좌표) , 시작 방향 d , 드래곤 커브의 세대 g가 주어진다.
• 방향은 0 은 오른쪽 방향, 1은 윗 방향, 2는 왼쪽 방향, 3은 아래 방향을 표시한다.
• 드래곤 커브가 보드판에 놓여질 때, 각각의 드래곤 커브의 점을 꼭지점으로 삼는 정사각형의 개수를 구하면 된다.

---

코드 리뷰

• 일단 세대가 n인 하나의 드래곤 커브가 그려진다 하면 그 드래곤 커브에서 그려질 수 있는 좌표의 개수는 2^n+1 개 가 된다.
• 모든 점의 개수는 0세대때 그려진 점, 1세대때 그려진 점, … n세대때 그려진 점들로 나뉜다.
• 0세대라고 했을 때, 점은 총 2개인데 시작점만 0세대로 하고, 두번째 점은 1세대 시작 점으로 한다.
• 1세대일 때 마지막 점 역시 2세대의 시작 점으로 고려한다.
• 그렇게 했을 때, 0세대는 점 1개, 1세대에만 해당되는 점 1개, 2세대에만 해당되는 점 2개 , 3세대는 4개 .. 식 으로 가게 된다.
• 이부분에서 약간 풀면서 꼬인 것 같은데 수정해보고 다시 올려봐야지.
• 아무튼 3세대 드래곤 커브의 점의 개수를 셀 때는, 0세대 1개, 1세대 1개, 2세대 2개, 3세대 4개 , 4세대 시작 점 1개를 만들면 된다.
• 각각의 좌표는 그 전 좌표에 방향을 더해준 값이 저장 된다.
• 각각의 좌표의 방향은 그 좌표가 속해있는 세대의 첫 점을 기준으로 좌표까지 거리만큼 세대 첫 점에서 반대로 그 거리만큼 떨어져있는 좌표의 방향 +1 을 해주면 되는 규칙을 찾았다.(대칭이라) (다른 분들은 더 쉬운 규칙을 찾은것 같던데.. 공부해야지..)
• 드래곤 커브 개수만큼 좌표를 check 배열에 저장하고, 마지막에 check 좌표 하나 잡고 정사각형 모양에 check 배열이 다 1인지 확인해보고 있으면 +1 하면된다.
• 문제 자체는 그닥 어렵지 않았는데 내 풀이가 약간 더러운 것 같다. 다음엔 좀더 깔끔하게 풀어봐야지.
• 시간 안에 해결 완료.

---

/* BOJ 15685 드래곤 커브*/

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

typedef struct {
	int x;
	int y;
	int d;
	int g;
}dragon_infor;

dragon_infor arr[22][1100];
int check[105][105];
int x, y, d, g;
int dc[4] = {0,-1,0,1};
int dr[4] = {1,0,-1,0};

void dragon_check(int idx, int level, int size) {
	for (level; level <= size; level++) {
		int tmp = (int)pow(2, level - 1);
		int num = 1;
		for (int i = (int)pow(2, level - 1); i <= (int)pow(2, level); i++) {
			if (num > tmp) {
				arr[idx][i].x = arr[idx][i - 1].x + dc[arr[idx][i - 1].d];
				arr[idx][i].y = arr[idx][i - 1].y + dr[arr[idx][i - 1].d];
				check[arr[idx][i].x][arr[idx][i].y] = 1;
				break;
			}
			arr[idx][i].x = arr[idx][i - 1].x + dc[arr[idx][i - 1].d];
			arr[idx][i].y = arr[idx][i - 1].y + dr[arr[idx][i - 1].d];
			check[arr[idx][i].x][arr[idx][i].y] = 1;
			if (arr[idx][(int)pow(2,level-1) - num].d == 3) arr[idx][i].d = 0;
			else {
				arr[idx][i].d = arr[idx][(int)pow(2,level-1) - num].d + 1;
			}
			num++;
		}
	}
}


int main() {
	int N;
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		scanf("%d%d%d%d", &arr[i][0].y, &arr[i][0].x, &arr[i][0].d, &arr[i][0].g);
		check[arr[i][0].x][arr[i][0].y] = 1;
		arr[i][1].x = arr[i][0].x + dc[arr[i][0].d];
		arr[i][1].y = arr[i][0].y + dr[arr[i][0].d];
		check[arr[i][1].x][arr[i][1].y] = 1;
		if (arr[i][0].d == 3) arr[i][1].d = 0;
		else arr[i][1].d = arr[i][0].d + 1;
	}
	for (int i = 1; i <= N; i++) {
		dragon_check(i,1, arr[i][0].g);
	}
	int ans = 0;
	for (int i = 0; i < 100; i++) {
		for (int j = 0; j < 100; j++) {
			if (check[i][j] == 1) {
				if (check[i][j + 1] == 1 && check[i + 1][j + 1] == 1 && check[i + 1][j] == 1) ans++;
			}
		}
	}
	printf("%d", ans);
	return 0;
}

---