백준 15685번 드래곤 커브 (삼성 기출)

문제

드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다.

1. 시작 점

2. 시작 방향

3. 세대

0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다. 아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다.

1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝 점에 붙인 것이다. 끝 점이란 시작 점에서 선분을 타고 이동했을 때, 가장 먼 거리에 있는 점을 의미한다.

2세대 드래곤 커브도 1세대를 만든 방법을 이용해서 만들 수 있다. (파란색 선분은 새로 추가된 선분을 나타낸다)

3세대 드래곤 커브도 2세대 드래곤 커브를 이용해 만들 수 있다. 아래 그림은 3세대 드래곤 커브이다.

즉, K(K > 1)세대 드래곤 커브는 K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시킨 다음, 그것을 끝 점에 붙인 것이다.

크기가 100×100인 격자 위에 드래곤 커브가 N개 있다. 이때, 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수를 구하는 프로그램을 작성하시오. 격자의 좌표는 (x, y)로 나타내며, 0 ≤ x ≤ 100, 0 ≤ y ≤ 100만 유효한 좌표이다.

입력

첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10)

입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 드래곤 커브는 서로 겹칠 수 있다.

방향은 0, 1, 2, 3 중 하나이고, 다음을 의미한다.

• 0: x좌표가 증가하는 방향 (→)

• 1: y좌표가 감소하는 방향 (↑)

• 2: x좌표가 감소하는 방향 (←)

• 3: y좌표가 증가하는 방향 (↓)

출력

첫째 줄에 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력한다.

 

처음에는 조건을 걸어서 시작점에서 90도로 회전시키는 방법등에 대한 알고리즘을 구하려고 했으나, 너무 복잡해지고 

이렇게 접근하는 문제가 아니라고 판단하였다.

그래서 단계가 상승함에 따라 방향이 어떻게 변화하는지 규칙성을 확인해보니 이전단계의 방향에 1을 더한뒤 역방향으로 바꾸어 뒤로 붙힌 형태였다. 

그렇게 방향이 변화함에 따른 좌표의 변화에 맞춰 visit를 찍어주고 정사각형 수를 찾아내면 되는 문제.

 

 

 

#include<iostream>
#include<vector>

using namespace std;


bool visit[101][101];




int main(void)
{
	int N;
	cin >> N;
	int result = 0;
	
	for(int i = 0; i < N; i++)
	{
		
		int x,y,d,g;
		
		cin >> x >> y >> d >> g;
		
		visit[y][x] = true;
		vector<int> vec;
		vec.push_back(d);
		
		
		for(int j = 0; j < g; j++)
		{
			vector<int> temp;
			temp = vec;
			for(int k = temp.size()-1; k>=0; k--)
			{
				vec.push_back((temp[k]+1)%4);
			}
		}
		
		for(int j = 0; j < vec.size(); j++)
		{
			if(vec[j] == 0)
			{
				x += 1;
			}
			else if(vec[j] == 1)
			{
				y -= 1;
			}
			else if(vec[j] == 2)
			{
				x -= 1;
			}
			else if(vec[j] == 3)
			{
				y += 1;
			}
			
			if(x>=0 && x <= 100 && y >= 0 && y <=100)
			{
				visit[y][x] = true;
			}
		}
		
		
	}
	
	for(int j = 0; j <= 100; j++)
	{
		for(int k = 0; k <= 100; k++)
		{
			if(k>=0 && k < 100 && j >= 0 && j < 100)
			{
				if(visit[j][k] && visit[j+1][k] && visit[j][k+1] && visit[j+1][k+1] )
				{
					result++;
				}
			}
		}
	}
		
		
		
	cout << result << endl;
		
		
	
	
	
}