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

문제 링크: https://www.acmicpc.net/problem/15685

 

구현 문제입니다. 드래곤커브를 만들어지는 규칙을 찾는 게 중요합니다.

 

3세대 드래곤 커브

드래곤 커브를 시작점부터 이동 방향에 따라 나타내보면 아래와 같습니다 

• 0세대: 0
• 1세대: 01
• 2세대: 0121
• 3세대: 01212321
• 4세대: 0121232123032321
• 5세대: 01212321230323212303010323032321
• ...

다음 세대로 갈 때, 전 세대의 경로를 역순으로 돌면서 \((x+1)\%4\) 한 값을 써주시면 됩니다. 0, 1, 2, 3 순으로 방향이 90도씩 반시계방향으로 가니, 90도를 회전한 값은 +1이 되겠죠. 4가 됐을 때 0이 되도록 모듈러 연산 해주시고요.

사실 원리만 알면 쉽습니다. 잘 떠오르지가 않아서 문제지..

 

\[
\begin{pmatrix}
x'\\y' 
\end{pmatrix}
=
\begin{pmatrix}
\cos \theta & - \sin \theta \\ 
\sin \theta & \cos \theta
\end{pmatrix}
\begin{pmatrix}
x \\
y
\end{pmatrix}
\]

저는 처음에 각 점의 좌표를 90도 회전해서 풀려고 했는데 공식도 잘 기억이 안나고 해서 출제자 의도대로(?) 풀었습니다. 회전 변환 하실 분은 위 공식 참고하시면 됩니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;


struct Dir {
  int y, x;
};

Dir DIR[4] = { {0,1},{-1,0},{0,-1},{1,0} };


int n;
bool visited[101][101];
vector<vector<int>> dragon_curves[4];


int main(int argc, char** argv)
{
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
#endif

  ios_base::sync_with_stdio(false);
  cin.tie(NULL);


  // 드래곤커브 만들기
  for (int d = 0; d < 4; ++d) {
    dragon_curves[d].push_back({ d });
    for (int i = 0; i < 10; ++i) {
      const vector<int>& prev_dragon = dragon_curves[d].back();
      vector<int> next_dragon = dragon_curves[d].back();

      for (auto it = prev_dragon.crbegin(); it != prev_dragon.crend(); ++it)
        next_dragon.push_back((*it + 1) % 4);
      dragon_curves[d].push_back(next_dragon);
    }
  }



  cin >> n;
  int x, y, d, g;
  for (int i = 0; i < n; ++i) {
    cin >> x >> y >> d >> g;
    visited[y][x] = true;
    const vector<int>& curve = dragon_curves[d][g];

    for (auto it = curve.cbegin(); it != curve.cend(); ++it) {
      y += DIR[*it].y;
      x += DIR[*it].x;

      visited[y][x] = true;
    }
  }

  int res = 0;
  for (int i = 0; i < 100; ++i)
    for (int j = 0; j < 100; ++j)
      if (visited[i][j] && visited[i][j + 1] && visited[i + 1][j] && visited[i + 1][j + 1])
        ++res;

  cout << res;
  

  return 0;
}

저는 0~10세대까지의 드래곤 커브 경로를 시작 방향별로 다 만들어놓고 사용했습니다.