[BOJ] #15685 _ 드래곤 커브

[드래곤 커브] https://www.acmicpc.net/problem/15685

15685번: 드래곤 커브

끝점을 기준으로 90도로 시계 방향 회전 시키면 값이 어떻게 바뀌는지 규칙을 찾아보았다.

 

끝점을 기준으로
- y값이 1감소하면, x값이 1감소한다.
- x값이 1증가하면, y값이 1감소한다.

새로운 좌표 x값 = 끝 점의 x좌표 + (끝 점 y좌표 - 과거 y좌표)
새로운 좌표 y값 = 끝 점의 y좌표 - (끝 점 x좌표 - 과거 x좌표)

# 예시
새로운 좌표 : (0, -1), 끝 점 : (1, -1), 과거 좌표 : (1, 0)
0 = 1 + (-1 - 0)
-1 = -1 - (1 - 1)

 

알아낸 규칙을 바탕으로 코드를 구현하였다.

curv 벡터에는 원래 드래곤 커브의 좌표 값을 저장하고, n_curv에는 새롭게 생길 드래곤 커브의 값을 저장한다.

 

모든 드래곤 커브의 좌표를 구한 후,

배열에 1로 표시하고, 사각형 모양으로 드래곤 커브를 확인하여 갯수를 세주는 방식으로 구현하였다.

 

[ 소스 코드 ]

#include <cstdio>
#include <vector>
#include <algorithm>
#define MAX 101

using namespace std;

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

void setDragonCurve(int x, int y, int d, int g);
int cntSquare();
int main() {
	int n;
	scanf("%d", &n);

	while (n--) {
		int x, y, d, g;
		scanf("%d %d %d %d", &x, &y, &d, &g);
		setDragonCurve(x, y, d, g);
	}

	printf("%d\n", cntSquare());

	return 0;
}

void setDragonCurve(int x, int y, int d, int g) {
	vector<pair<int, int> > curve;
	curve.push_back(make_pair(x, y));
	map[y][x] = 1;
	curve.push_back(make_pair(x + dx[d], y + dy[d]));
	map[y + dy[d]][x + dx[d]] = 1;

	while (g--) {
		int end_point = curve.size() - 1;
		int tmp_x = curve[end_point].first, tmp_y = curve[end_point].second;
		int dist_x, dist_y;

		while (end_point > 0) {
			dist_x = curve[end_point].first - curve[end_point - 1].first;
			dist_y = curve[end_point].second - curve[end_point - 1].second;
			tmp_x += dist_y;
			tmp_y -= dist_x;
			curve.push_back(make_pair(tmp_x, tmp_y));
			map[tmp_y][tmp_x] = 1;

			end_point--;
		}
	}
}

int cntSquare() {
	int result = 0;
	for (int i = 0; i < MAX-1; i++) {
		for (int j = 0; j < MAX-1; j++) {
			if (!map[i][j]) continue;
			if (!map[i + 1][j]) continue;
			if (!map[i][j + 1]) continue;
			if (!map[i + 1][j + 1]) continue;
			result++;
		}
	}
	return result;
}