[BOJ/백준 15685/C++] 드래곤 커브

https://www.acmicpc.net/problem/15685

15685번: 드래곤 커브

[문제 요약]

- 드래곤 커브는 세 가지 속성으로 이루어져 있다. ( 시작 점, 시작 방향 , 세대 )

- x축은 → 방향 y축은 ↓ 방향이다.

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

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

- 2세대 드래곤 커브

- 3세대 드래곤 커브

- 즉 K세대 (K>1) 드래곤 커브는 K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전시킨 다음, 그것을 끝 점에 붙인 것이다. 크기 100x100 격자 위에 드래곤 커브가 N개 있다. 크기가 1x1인 정사각형의 네 꼭짓점이 모두 드래곤커브의 일부인 정사각형의 개수를 구하여라

 

[문제 조건]

- 첫째 줄에 드래곤 커브의 개수 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좌표가 증가하는 방향 (↓)

 

[문제 풀이]

(mp는 격자판의 꼭짓점 사용여부를 나타내는 2차원 배열)

 

먼저 격자판은 2차원배열의 형태로 생각했다. mp의 값은 좌표가 드래곤 커브에 사용되는 꼭짓점인지 아닌지 사용여부를 나타내는 bool형의 2차원 배열이다.

 

그 다음 과정은 예제를 통해 설명하겠다.

문제의 첫 번째 예제의 두 번째 경우(4, 2, 1, 3)을 예를들어 점을 찍는 방법을 서술하겠다.

1세대까지 진행시켰을 때 시작점 부터 좌표를 적어보면 (2,4) → (1,4) → (1,3) 이고 방향은 1 → 2이다.

여기서 2세대까지 진행시키면

이와 같은 그림이 되고 좌표는 (2,4) → (1,4) → (1,3) → (2,3) → (2,2)이고 방향은 1 → 2 → 3 → 2 가 된다

여기서 본인이 찾은 규칙을 설명하자면

K-1세대까지 방향을 저장해 놓은 배열의 마지막 값부터 처음 까지 위 그림을 기준으로 시계방향으로 한칸 이동 후 반대편의 값이 다음 방향이 된다.

 

무슨 뜻이냐 1세대 까지 진행시켰을 때 방향을 보면 1→2로 저장해놨을 것이다. 여기서 2부터 확인해 보면, 위 그림을 기준으로 2의 시계방향은 1이다. 그 다음 반대편 값은 3이다. 그리고 1 → 2 → 3 와 같이 배열에 추가해준다. 나머지 1도 똑같이 하면 1→2→3→2가 저장되어 있을 것이다.

 

그리고 이 배열을 좌표 배열에 대응시켜 생각해보면

 (2,4) → (1,4) → (1,3) 

     1  →     2   →    3    →   2

와 같은 상태일텐데 여기서 각 좌표는 대응되는 방향을 저장해둔 배열의 값 방향으로 이동시키면 다음 좌표가 된다.

(그림판으로 그려서 퀄리티가 좀 그래도 이해해주세요)

그림과 같이 다음 좌표들을 좌표배열 뒤에 계속 추가해주면 된다.

이런 방식으로 격자판에 true값으로 바꿔주면 드래곤 커브를 모두 표시할 수 있다.

 

그 다음 네 꼭짓점 모두 드래곤커브의 일부가 되는 정사각형을 찾는 방법은 아주 간단하다

모든 격자판을 확인하면서 현재 좌표가 (y,x)일때 (y,x) , (y,x+1) , (y+1,x) , (y+1,x+1)이 모두 true값이면 네 꼭짓점 모두 드래곤커브이 일부가 되는 정사각형이란 뜻이다.

 

[소스 코드]

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <deque>
#include <math.h>
#include <map>
#include <queue>
#include <stack>

using namespace std;

int N;
vector<vector<bool>> mp;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,-1,0,1 };

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

	mp.resize(101);
	for (int i = 0; i <= 100; i++) mp[i].resize(101);

	cin >> N;

	while (N--)
	{
		int x, y, d, g;
		cin >> x >> y >> d >> g;

		vector<pair<int, int>> dt;
		vector<int> direct;

		direct.push_back(d);
		dt.push_back({ y,x });
		dt.push_back({ y + dy[d], x + dx[d] });
		mp[y][x] = 1;
		mp[y + dy[d]][x + dx[d]] = 1;
		int direct_pos = 1;
		int direct_cnt = 1;
		for (int i = 0; i < g; i++)
		{
			for (int j = direct.size() - 1; j >= 0; j--)
			{
				int tmp = direct[j];
				if (tmp == 0) tmp = 3;
				else tmp--;

				tmp = (tmp + 2) % 4;
				direct.push_back(tmp);
			}
			for (int j = direct_pos; j < direct.size(); j++)
			{
				dt.push_back({ dt[j].first + dy[direct[j]], dt[j].second + dx[direct[j]] });
				mp[dt[j].first + dy[direct[j]]][dt[j].second + dx[direct[j]]] = 1;
				direct_pos = j;
			}
			direct_pos++;
		}
	}
	int ans = 0;
	for (int i = 0; i <= 99; i++)
	{
		for (int j = 0; j <= 99; j++)
		{
			if (mp[i][j] == 1 && mp[i + 1][j] == 1 && mp[i][j + 1] == 1 && mp[i + 1][j + 1] == 1)
				ans++;
		}
	}
	cout << ans;
}

 

굳