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

www.acmicpc.net/problem/15685

15685번: 드래곤 커브

다음 세대의 드래곤 커브를 만들 때 포인트 지점을 정해서 현재까지 만들어진 드래곤 커브의 지점들과의 거리를 구한 뒤, 포인트 지점을 기준으로 회전을 하여 구한다. 각 세대의 포인트 지점은 현재까지 만들어진 드래곤 커브의 마지막 지점이다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;

int n;
int board[101][101]; //y,x

void CheckGc(pair<int, int> point, int remain, vector<pair<int, int>> now_gc)
{
	//더 이상 해당 드래곤커브가 만들어질게 없을때
	if (remain == 0)
		return;

	pair<int, int> distance;
	pair<int, int> next;
	vector<pair<int, int>> maked_gc;

	for (int i = 0; i < now_gc.size() - 1; i++)
	{
		distance = make_pair(now_gc[i].first - point.first, now_gc[i].second - point.second); //만들어진 드래곤 커브의 지점과 point지점과의 거리를 구한다
		next = make_pair(point.first + distance.second, point.second - distance.first); //구한 거리를 통해 다음에 만들어지는 드래곤 커브의 지점을 구한다

		board[next.first][next.second] = 1; //만들어진 지점을 체크한다
		maked_gc.push_back(next); //이번에 만들어진 드래곤커브 지점을 저장
	}

	//이번에 만들어진 드래곤 커브의 지점은 이미 만들어진 드래곤 커브의 첫번째 지점부터 거리를 통해 만들어진것 이므로
	//이번에 만들어지는 드래곤 커브는 순서가 역순으로 만들어진것이므로 순서를 뒤집는다
	reverse(maked_gc.begin(), maked_gc.end());

	for (int i = 0; i < maked_gc.size(); i++)
		now_gc.push_back(maked_gc[i]); //이번에 만들어진 드래곤 커브를 현재 만들어지는 드래곤커브에 저장한다

	//현재까지 만들어진 드래곤 커브의 마지막 지점이 다음 만들어질때 point지점
	pair<int, int> next_point = now_gc[now_gc.size() - 1];

	//다음 세대 드래곤 커브 만들어서 체크하기
	CheckGc(next_point, remain - 1, now_gc);
}

//개수를 센다
int Solve()
{
	int ret = 0;

	for (int i = 0; i <= 99; i++)
	{
		for (int j = 0; j <= 99; j++)
		{
			if (board[i][j] == 1 && board[i][j + 1] == 1 && board[i + 1][j] == 1 && board[i + 1][j + 1] == 1)
				ret++;
		}
	}

	return ret;
}

void Pre()
{
	for (int i = 0; i <= 100; i++)
		for (int j = 0; j <= 100; j++)
			board[i][j] = 0;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	Pre();

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int x, y, d, g;
		pair<int, int> point;
		vector<pair<int, int>> now_gc;

		cin >> x >> y >> d >> g;

		board[y][x] = 1; //board에 지점 체크
		now_gc.push_back(make_pair(y, x)); //현재 드래곤 커브에 해당 지점 넣기

		//방향에 따라 만들어지는 지점 설정
		if (d == 0)
			point = make_pair(y, x + 1);

		else if (d == 1)
			point = make_pair(y - 1, x);

		else if (d == 2)
			point = make_pair(y, x - 1);

		else if (d == 3)
			point = make_pair(y + 1, x);

		board[point.first][point.second] = 1; //board에 지점 체크
		now_gc.push_back(point); //현재 드래곤 커브에 point 지점 넣기

		//해당 드래곤 커브가 만들어 지는 지점 체크
		CheckGc(point, g, now_gc);
	}

	cout << Solve();

	return 0;
}