[백준] 드래곤 커브 - 15685

문제를 풀기 위해서는 점회전에 대해 알고 있어야 합니다.

 

문제에서는 원점을 기준으로 시계방향으로 90도 회전하도록 되어있지만

주어진 그래프의 점들의 자표는 x축 대칭되어 있으므로 반시계방향으로 90도 회전한다 생각할 수 있습니다.

 

따라서 원점을 기준으로 90도 회전할 경우 아래와 같은 방법으로 값을 구할 수 있습니다.

x' = 0 - y * Sin(90˚)
y' = x * Sin(90˚) + 0

 

하지만 문제에서 원하는 회전은 원점이 아닌 끝 점을 통해 회전하기를 원하므로

x값과 y값에 해당 점만큼 원점을 향해 이동시켜 준 후 회전시켜야 합니다.

이후 다시 이동한 거리만큼 되돌려주는 방식을 통해 회전된 점의 위치를 구할 수 있습니다.

 

각 세대별 끝점은 이전 세대를 계산하는 과정에서 가장 먼저 생성된 점이 됩니다.

 

풀이 코드

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

typedef pair<int, int> pii;
typedef vector<pii> vpii;

bool grid[101][101] = {};

pii rotate(pii p, pii rot)
{
  int rotX = rot.first;
  int rotY = rot.second;
  int pX = p.first - rotX;
  int pY = p.second - rotY;
  return make_pair(-pY + rotX, pX + rotY);
}
void makeNextGeneration(vpii &dragon, pii endPoint, int depth, const int endDepth)
{
  if (depth == endDepth)
  {
    return;
  }
  int len = dragon.size();
  pii newEndPoint;
  for (int i = 0; i < len; i++)
  {
    pii newPoint = rotate(dragon[i], endPoint);
    if (i == 0)
    {
      newEndPoint = newPoint;
    }
    int newX = newPoint.first;
    int newY = newPoint.second;
    if (newX >= 0 && newX <= 100 && newY >= 0 && newY <= 100)
    {
      grid[newX][newY] = true;
    }
    dragon.push_back(newPoint);
  }

  makeNextGeneration(dragon, newEndPoint, depth + 1, endDepth);
}

int main()
{
  // freopen("input.txt", "r", stdin);
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int curvNum;
  cin >> curvNum;
  int dx[4] = {1, 0, -1, 0};
  int dy[4] = {0, -1, 0, 1};
  for (int i = 0; i < curvNum; i++)
  {
    int x, y, d, g;
    vpii dragon;
    cin >> x >> y >> d >> g;
    grid[x][y] = true;
    int endX = x + dx[d];
    int endY = y + dy[d];
    grid[endX][endY] = true;

    dragon.push_back(make_pair(x, y));
    dragon.push_back(make_pair(endX, endY));
    makeNextGeneration(dragon, make_pair(endX, endY), 0, g);
  }
  int ans = 0;
  for (int i = 0; i < 100; i++)
  {
    for (int j = 0; j < 100; j++)
    {
      if (grid[i][j] && grid[i + 1][j] && grid[i][j + 1] && grid[i + 1][j + 1])
      {
        ans++;
      }
    }
  }
  cout << ans;
  return 0;
}