[백준] 15685번: 드래곤 커브

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

15685번: 드래곤 커브

문제 이해

이걸 대체 어떻게 그림을 그려야하지 싶어서 바로 검색을 했다.

 

이 드래곤 커브는 패턴을 가지고 있다. 예를 들어 처음 방향이 0이면

• 0세대: 0
• 1세대: 0 1
• 2세대: 01 21
• 3세대: 0121 2321
• 4세대: 01212321 23032321
• ....

로 이어진다.

즉 1세대는 0세대 커브 + 0세대 커브를 역으로 읽으며 거기에 1을 더한 값이다 ( 0121 -> 2321 )

 

1. 방향(d)와 세대(g)를 받아서 커브의 모양을 방향을 저장하는 배열 dir에 정리해주고, (Add_Direction())
   
   
2. 시작점에서부터 그 방향을 따라가면서 map에 꼭짓점을 1로 표시해주면 된다. (Draw_Curve()) 
   나는 디버깅을 편히 하려고 c라는 값을 대신 넣어주었다.
   
   
3. 마지막으로 맵을 탐색하면서 꼭짓점이 모두 4인 칸,
   즉 (i,j) (i, j+1), (i+1, j), (i+1, j+1) 이 모두 4인 경우를 세주면 된다 (Count_Rects())

주의할 점

내가 맨날 헷갈리는 좌표....

입력으로 (X, Y) 가 주어지는데, X가 열이고 Y가 행인데, 입력을 X, Y순으로 받는다

작성 코드

#include <stdio.h>
#include <string.h>
#define SIZE 100

int N; 
int map[SIZE + 5][SIZE + 5];
int dir[1024 + 5];
int d_size = 0;

int dy[] = { 0, -1, 0, 1 };
int dx[] = { 1, 0, -1, 0 };

void Add_Direction(void) {
	int end = d_size;
	for (int i = 0; i < end; i++) {
		dir[end+(end-i-1)] = (dir[i] + 1) % 4;
	}
	d_size *= 2;
}

void Draw_Curve(int y, int x, int d, int g, int c) {
	memset(dir, 0, sizeof(dir));
	d_size = 1;
	dir[0] = d;
	int ny = y, nx = x;
	map[y][x] = c;
	for (int i = 0; i < g; i++) {
		Add_Direction();
	}
	/*
	for (int j = 0; j < d_size; j++) {
		printf("%d ", dir[j]);
	}
	printf("\n");
	*/

	for (int i = 0; i < d_size; i++) {
		ny += dy[dir[i]];
		nx += dx[dir[i]];
		map[ny][nx] = c;
	}
}

int Count_Rects(void) {
	int cnt = 0;
	for (int i = 0; i <= 100; i++) {
		for (int j = 0; j <= 100; j++) {
			if (map[i][j] == 0) continue;
			if (map[i][j + 1] == 0) continue;
			if (map[i + 1][j] == 0) continue;
			if (map[i + 1][j + 1] == 0) continue;
			cnt++;
		}
	}
	return cnt;
}

int main(void) {
	int y, x, d, g;
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d %d %d %d", &x, &y, &d, &g);
		Draw_Curve(y, x, d, g, i+1);
	}
	printf("%d", Count_Rects());
	return 0;
}