🙇‍♀️[Gold III] 드래곤 커브 - 15685

문제 링크

성능 요약

메모리: 2240 KB, 시간: 0 ms

분류

구현, 시뮬레이션

제출 일자

2024년 2월 14일 18:00:47

문제 설명

드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 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인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력한다.

🚀풀이

3시간 걸림.

드래곤 커브의 회전은 기준점을 0, 0으로 만든 다음 회전을 했다.

기준점은 배열의 첫번째로 정해지는데 함수를 보면 더 이해가 된다.

void dragonCurve(int x, int y, int d, int g)
{
	vector<pair<int, int>> v;
	v.push_back({ y, x });

	int ny = y + dy[d];
	int nx = x + dx[d];
	v.push_back({ ny, nx });

	// ny, nx를 기준으로 돌려야한다.
	pair<int, int> endPoint = v.back(); // 이게 기준점
	int endPointY = endPoint.first;
	int endPointX = endPoint.second;
    // 0세대일땐 끝이 기준점이 된다.

	// 시계 방향으로 회전은
	// 기준점에서 x차이랑 y차이 
	// 기준을 0,0 으로 만든 뒤 계산하게 쉽게 만들기

	int nEndPointY = 0, nEndPointX = 0;
	for (int k = 0; k < g; ++k)
	{
		int vSize = v.size();
		for (int i = 0; i < vSize; ++i)
		{
			int viy = v[i].first;
			int vix = v[i].second;

            // 같은 점을 돌리면 그냥 그대로니까 스킵
			if (viy == endPointY && vix == endPointX)
				continue;

			// 0, 0을 기준으로 초기화
			viy -= endPointY;
			vix -= endPointX;

            // 회전
			int toAddY = vix;
			int toAddX = -viy;

			// 그 뒤 변한 값들을 더해주기
			toAddY += endPointY;
			toAddX += endPointX;

			// 0번째가 다음 기준점이 된다.
			if (i == 0)
			{
				nEndPointY = toAddY;
				nEndPointX = toAddX;
			}

			visited[toAddY][toAddX] = 1;
			v.push_back({ toAddY, toAddX });
		}

		endPointY = nEndPointY;
		endPointX = nEndPointX;
	}

	for (int i = 0; i < v.size(); ++i)
	{
		board[v[i].first][v[i].second] = 1;
	}
}

정답을 구하는 건 네 꼭지점이 드래곤 커브의 일부인 것이므로 아래와 같이 함수를 만들었다.

int getResult()
{
	// 네 꼭지점이 드래곤 커브의 일부인 것의 개수

	int res = 0, num = 100;

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

	return res;
}

i, j 가 0부터 순회해야하는데 1부터인줄 알고 한참 해멨다..

문제에서도 0,0에서 시작하는데 왜 1,1 부터라고 생각했는지..

밑의 전체 코드에선 visited가 있는데 처음엔 board로 바로 계산하면 전체가 움직일거라고 생각해서 visited를 만들고 나중에 복사할 생각이였는데, 드래곤 커브 함수 내에서 벡터를 만들어서 이 부분을 다르게 해결했다.

image

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

void printBoard();

//
// 드래곤 커브
// 
// 0: x좌표가 증가하는 방향 (→)
// 1: y좌표가 감소하는 방향(↑)
// 2 : x좌표가 감소하는 방향(←)
// 3 : y좌표가 증가하는 방향(↓)
// 
// x, y, d, g
// x = x시작 좌표
// y = 시작 y좌표
// d = 방향
// g = 세대값
//

int dy[] = { 0, -1, 0, 1 };
int dx[] = { 1, 0, -1, 0 };
int board[105][105];
int visited[101][101]; // 하나하나 그릴거니까 필요할듯

// 현재까지 그린것에서 90도 돌려서 그리는게 필요


void dragonCurve(int x, int y, int d, int g)
{
	// 주어진 정보값으로 드래곤 커브를 
	// g번 돌리기... 흠..그린다.
	// 어떻게 그릴까

	vector<pair<int, int>> v;

	visited[y][x] = 1;
	v.push_back({ y, x });

	int ny = y + dy[d];
	int nx = x + dx[d];
	visited[ny][nx] = 1;
	v.push_back({ ny, nx });

	// ny, nx를 기준으로 돌려야한다.
	// 끝점을 아는 방법은? 벡터의 끝? 기준점에서 회전한다 
	pair<int, int> endPoint = v.back(); // 이게 기준점
	int endPointY = endPoint.first;
	int endPointX = endPoint.second;


	// 시계 방향으로 회전은
	// 기준점에서 x차이랑 y차이 
	// 기준을 0,0 으로 만든 뒤 계산하게 쉽게 만들기

	int nEndPointY = 0, nEndPointX = 0;
	for (int k = 0; k < g; ++k)
	{
		int vSize = v.size();
		for (int i = 0; i < vSize; ++i)
		{
			int viy = v[i].first;
			int vix = v[i].second;

			if (viy == endPointY && vix == endPointX)
				continue;

			// 0, 0을 기준으로 초기화
			viy -= endPointY;
			vix -= endPointX;

			int toAddY = vix;
			int toAddX = -viy;

			// 그 뒤 변한 값들을 더해주기
			toAddY += endPointY;
			toAddX += endPointX;

			// 0번째가 다음 기준점이 된다.
			if (i == 0)
			{
				nEndPointY = toAddY;
				nEndPointX = toAddX;
			}

			visited[toAddY][toAddX] = 1;
			v.push_back({ toAddY, toAddX });
		}

		endPointY = nEndPointY;
		endPointX = nEndPointX;
	}

	for (int i = 0; i < v.size(); ++i)
	{
		board[v[i].first][v[i].second] = 1;
	}

	//printBoard();
	//cout << endl;

	//for (int i = 1; i <= 10; ++i)
	//{
	//	for (int j = 1; j <= 10; ++j)
	//	{
	//		board[i][j] = 0;
	//	}
	//}

	// visited 정보값을 board에 적용하기
}

void visitedClear()
{
	for (int i = 1; i <= 100; ++i)
	{
		for (int j = 1; j <= 100; ++j)
		{
			visited[i][j] = 0;
		}
	}
}

void printBoard()
{
	int num = 100;

	for (int i = 1; i <= num; ++i)
	{
		for (int j = 1; j <= num; ++j)
		{
			cout << board[i][j];
		}

		cout << '\n';
	}
}

int getResult()
{
	// 네 꼭지점이 드래곤 커브의 일부인 것의 개수

	int res = 0, num = 100;

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

	return res;
}

void solve()
{
	int n;
	cin >> n;

	int x, y, d, g;
	for (int i = 0; i < n; ++i)
	{
		cin >> x >> y >> d >> g;

		dragonCurve(x, y, d, g);
	}

	cout << getResult();
	//printBoard();

}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}

참고