[백준 - 15685] 드래곤 커브

||문제 이해

이차원 좌표 평면에서 시작된다. (x,y는 uv좌표계와 같은 방향을 가지고 있다.)

 

드래곤 커브는 속성을 기반으로 세대마다 길어진다.

여러 드래곤 커브가 있고 특정 세대까지 길어질 때,

1 * 1 정사각형의 꼭짓점이 드래곤 커브에 속하는 개수를 구하라.

---

||해결 계획

제일 먼저 든 생각은

모든 드래곤 커브의 꼭짓점을 구할 수 있는가? 였다,

그 꼭짓점들을 배열에 저장하고 싶었다.

 

그리고 간단한 판을 생각했다.

일단 드래곤 커브의 속성인지 뭔지는 중요하지 않고 빨간색이 드래곤 커브에 해당한 꼭짓점이라 하면

좌측 상단의 칸부터 정사각형이 될 수 있는지 검사하면 간단하다고 생각했다.

 

즉 부분 문제를 세가지로 나누었다.

1. 드래곤 커브 생성하기

2. 드래곤 커브에 속한 꼭짓점 저장하기

3. 판의 좌측 상단부터 정사각형 검사하기

 

코드를 대강 작성해보자

코드를 작성하다 보니까 굳이 100 * 100개의 꼭짓점을 검사해야싶나 했다.

그래서 드래곤 커브에 속한 꼭짓점만 검사하기로 했다.

 

여기서 set을 사용한 이유는 위에서 사각형 검사를 할때 중복으로 검사하지 않게 하고 싶어서 그렇다.

---

||계획 검증

 

일단 3 * 3판에 모든 드래곤 커브의 좌표가 빨간 좌표에 생겼다고 하자.

1.MakeDC( )를 하면 드래곤 커브를 생성하면서 저 빨간 점들이 저장될 것이다.

위의 예시라면 밑과 같이 저장이 될 것이다.

vector<pair<int,int>> vertices ={ {1, 1}, {1, 2}, {2, 1}, {2, 2}, {2, 3}, {3, 3} } 

 

 

2.CheckRect( )에서 vertices에 저장한 빨간 점을 모두 탐색한다.

└2.1 각 원소의 우측, 하단, 우측하단이 vertices에 저장되어있는지 확인하고 모두 있으면 카운트 한다.

(이 세가지만 확인함으로서 찾는 사각형이 중복되는걸 방어했다)

{1, 1} = {2, 1}, {1, 2}, {2, 2} = 카운트O

{1, 2} = {2, 2}, {1, 3}, {2, 3} = 카운트X

{2, 1} = {3, 1}, {2, 2}, {3, 2} = 카운트X

{2, 2} = {3, 2}, {2, 3}, {3, 3} = 카운트X

{2, 3} = {3, 3}, {2, 4}, {3, 4} = 카운트X

{3, 3} = {4, 3}, {3, 4}, {4, 4} = 카운트X

 

최종 1개로 답이 도출된다.

 

흠.. 일단 검증 같은걸 해보긴 했는데 이걸 검증이라고 할 수 있는지? 모르겠다

---

||구현

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
set<pii> vertices;

pii operator+(const pii & p1, const pii & p2)
{
	return { p1.first + p2.first, p1.second + p2.second };
}
pii operator-(const pii & p1, const pii & p2)
{
	return { p1.first - p2.first, p1.second - p2.second };
}
pii Rotate(pii & p)
{
	int temp = (p.second * -1);
	p.second = p.first;
	p.first = temp;
	return p;
}

//[0] : 시작 x좌표
//[1] : 시작 y좌표
//[2] : 시작 방향
//[3] : 세대
vector<vector<int>> dcProp;
vector<pii> tdc;

pii moving[4] = { {1, 0},{0, -1},{-1, 0}, {0, 1} };
void MakeDC()
{
	//1. 드래곤 커브를 개수만큼 생성한다.
	for (const auto & d : dcProp)
	{
		//1.1 0세대의 시작 좌표 저장
		pii s = { d[0], d[1] };
		tdc.push_back(s);
		//1.2 0세대의 끝점 계산, 좌표 기록
		tdc.push_back(s + moving[d[2]]);

		//1.3 세대가 성장하는가?
		if (0 < d[3])
		{
			//1.3.1	2세대이상부터, 입력 세대 만큼 커브 성장
			for (int i = 1; i <= d[3]; ++i)
			{
				pii e = tdc.back();
				int tempSize = tdc.size();
				//이전까지의 꼭짓점 회전 시켜 좌표 기록
				for (int j = tempSize - 2; 0 <= j ; --j)
				{
					pii t = tdc[j] - e;
					tdc.push_back(e + Rotate(t));
				}
			}
		}

		//최종 저장
		for (const auto & d : tdc)
		{
			vertices.insert(d);
		}
		tdc.resize(0);
	}
}

// (x, y) 형태의 좌표
pii preset[3] = { {1, 0}, {0, 1}, {1, 1} };
int ret = 0;
void CheckRect()
{
	//1. 각 꼭짓점 검사
	for (auto & d : vertices)
	{
		bool isRect = true;
		for (int i = 0; i < 3 && isRect; ++i)
		{
			if (vertices.find(d + preset[i]) == vertices.end()) isRect = false;
		}

		if (isRect == true) ++ret;
	}
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);

	int c; cin >> c;
	dcProp.resize(c);
	for (int i = 0; i < c; ++i)
	{
		dcProp[i].resize(4);
		cin >> dcProp[i][0] >> dcProp[i][1] >> dcProp[i][2] >> dcProp[i][3];
	}
	MakeDC();
	CheckRect();

	cout << ret;
	return 0;
}

---

||되돌아보기

막힌 부분이 두 부분이 있었다.

 

1.문제의 조건을 잘못 이해

문제를 풀면서 점점 내가 문제를 이해 완벽히 이해하지 못한다고 생각이 들었다.

코드는 완성했는데 예시의 답과는 다르게 나오고,

조건이 틀렸는지 확인하고, 틀린 조건 수정하고 => 이 단계 반복이 좀 많았다;

 

문제 조금보고 이해했다고 깝치지말고 

다음에는 내가 이해한 것과 예시가 같은지도 제대로 비교해서 문제를 확실히 이해하고 넘어가야겠다😪

 

2.다양한 예시

내가 0세대에서 1세대로 넘어가는 예시만 생각하는 바람에

끝 좌표 이전의 모든 좌표를 회전시켜서 저장하지 못하고 시작 좌표만 회전시켜서 저장되었다.

 

너무 많은 예시는 아니더라도 최소 2개정도의 예시를 생각하자

---

||개선 코드

내 코드에서 일단 가볍게 개선 해봤다.

일단 회전 부분을 (y * -1, x)으로 간단히 했고

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

//[0] : start X //[1] : start Y //[2] : 시작 방향 //[3] : 세대
vector<vector<int>> dcProp;
set<pii> vertices;
vector<pii> tdc;

pii operator+(const pii & p1, const pii & p2)
{
	return { p1.first + p2.first, p1.second + p2.second };
}
pii operator-(const pii & p1, const pii & p2)
{
	return { p1.first - p2.first, p1.second - p2.second };
}

pii moveSet[4] = { {1, 0},{0, -1},{-1, 0}, {0, 1} };
void MakeDC()
{
	//1. 드래곤 커브를 개수만큼 생성한다.
	for (const auto & d : dcProp)
	{
		//1.1 0세대의 시작, 끝 좌표 저장
		pii s = { d[0], d[1] };
		tdc.push_back(s);
		tdc.push_back(s + moveSet[d[2]]);

		//1.2 1세대이상부터, 입력 세대 만큼 커브 성장
		for (int i = 1; i <= d[3]; ++i)
		{
			pii e = tdc.back();
			int tempSize = tdc.size();

			//1.2.1 끝점 이전의 꼭짓점들 회전 시켜 좌표 기록
			for (int j = tempSize - 2; 0 <= j ; --j)
			{
				pii t = tdc[j] - e;
				tdc.push_back(e + make_pair(t.second * -1, t.first));
			}
		}

		//최종 저장
		for (const auto & d : tdc)
		{
			vertices.insert(d);
		}
		tdc.resize(0);
	}
}

pii checkSet[3] = { {1, 0}, {0, 1}, {1, 1} };
int CheckRect()
{
	int ret = 0;
	//저장한 각 꼭짓점 검사
	for (auto & d : vertices)
	{
		bool isRect = true;
		for (int i = 0; i < 3 && isRect; ++i)
		{
			if (vertices.find(d + checkSet[i]) == vertices.end()) isRect = false;
		}
		if (isRect == true) ++ret;
	}
	return ret;
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);

	//1. Input values
	int c; cin >> c;
	dcProp.resize(c);
	for (int i = 0; i < c; ++i)
	{
		dcProp[i].resize(4);
		cin >> dcProp[i][0] >> dcProp[i][1] >> dcProp[i][2] >> dcProp[i][3];
	}

	//2. Do calculate & Print result
	MakeDC();
	cout << CheckRect();
	return 0;
}