[백준 15685] 드래곤 커브

문제 바로가기

15685번: 드래곤 커브

 

엄청 재밌는 문제였다.

읽고 문제 이해하는 데 한참 걸렸는데 규칙을 찾으니까 신기했다.

 

세대가 하나 증가할 때마다 그 전 세대의 벡터의 방향들을 하나씩 증가시켜서 거꾸로 저장하면 된다.

 

벡터의 방향을 모두 저장해두고 벡터의 size 만큼 반복하면서

현재 위치에서 저장된 방향으로 이동시킨다.

정사각형을 만드는 지 확인해야하니까 이동시키면서 각 위치는 map이라는 2차원 배열에 저장해두었다.

 

그리고 마지막으로, 정사각형을 만드는 지 확인만 해주면 끝 ~

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <queue>
#include <math.h>

using namespace std;

int n;
int x, y, d, g;
int map[100][100];
int pos[4][2] = { {1,0}, {0,-1}, {-1,0}, {0,1} };

void solve()
{
	vector<int> dir;
	map[x][y] = 1;
	dir.push_back(d);

	for (int ng = 0; ng < g; ng++)
	{
		for (int i = dir.size() - 1; i >= 0; i--)
		{
			dir.push_back((dir[i] + 1) % 4);
		}
	}

	int prev_x = x;
	int prev_y = y;

	for (int i = 0; i < dir.size(); i++)
	{
		int nx = prev_x + pos[dir[i]][0];
		int ny = prev_y + pos[dir[i]][1];

		map[nx][ny] = 1;

		prev_x = nx;
		prev_y = ny;
	}
	
}
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> x >> y >> d >> g;
		solve();
	}

	int square_cnt = 0;
	for (int i = 0; i < 100; i++)
	{
		for (int j = 0; j < 100; j++)
		{
			if (map[i][j] == 1 && map[i][j + 1] == 1 && map[i + 1][j] == 1 && map[i + 1][j + 1] == 1)
				square_cnt++;
		}
	}

	cout << square_cnt << endl;
}