[BOJ] 드래곤커브

[문제]

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

15685번: 드래곤 커브

[풀이]

 

1) 방향은 총 4가지이고 각 세대 별로 어떤 방향으로 나아가는지 파악한다.

 

드래곤 커브의 좌표와 세대의 범위는  (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10) 위와 같으므로 gen[4][1025]를  두고 각 방향별로 어떤 방향으로 나아가는 지 파악한다. 

 

0	0
1	0 1
2	0 1 2 1
3	0 1 2 1 2 3 2 1
4	0 1 2 1 2 3 2 1 2 3 0 3 2 3 2 1
...

• 세대의 증가에 따라 배열의 수는 2의 등비수열로 증가. (0세대일때는 2^0 / 1세대는 2^1 -> 즉 10세대는 2^10개.)
• 각 세대의 방향은 이전 세대의 방향 리스트의 역에서 +1을 한 것과 같다. (1세대 0 1 -> 2세대 0 1 1+1 0+1 => 0 1 2 1)

2) 각 방향에 따라서 각 세대의 방향을 저장해서 시작 꼭짓점에 따라 해당 방향으로 이동하면서 맵에 표시한다. 

 

3) 네 꼭짓점이 모두 드래곤커브의 일부가 되는 개수를 구하라고 했기 때문에 맵을 돌면서 (i, j) (i+1, j) (i+1, j+1) (i, j+1)이 모두 0보다 크다면 드래곤 커브의 일부이기 때문에 res을 1만큼 증가한다. 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93

#include <iostream> #include <vector> #include <cmath> using namespace std; int n; bool map[101][101]; typedef struct Dragon {     int x, y, d, g;     Dragon(int _x, int _y, int _d, int _g) : x(_x), y(_y), d(_d), g(_g){}; } D; int gen[1<<10+1][4]; vector<D> lines; int dx[4] = {1, 0, -1, 0}, dy[4] = {0, -1, 0, 1}; int pow(const int &a) {     return 1<<a; }   void drawLines(D now) {     int cnt = (int)pow(now.g);           int x = now.x;     int y = now.y;     map[y][x] = 1;     for (int i = 0; i < cnt; i++) {         switch (gen[i][now.d]) {             case 0 :             x++;             break;             case 1:             y--;             break;             case 2:             x--;             break;             case 3:             y++;             break;         }         map[y][x] = 1;     } }   void makeGens() {       for (int d = 0; d < 4; d++)     {         gen[0][d] = d; //0세대         for (int i = 1; i <= 10; i++)         {             int prevCnt = (int)pow(i - 1);             // int nowCnt = (int)pow(i, 2);               for (int j = 0; j < prevCnt; j++)             {                 gen[prevCnt + j][d] = gen[prevCnt - j - 1][d] + 1 > 3 ? 0 : gen[prevCnt - j - 1][d] + 1;             }         }     } } int findSqaures() {     int res = 0;     for (int i = 0; i < 100; i++) {         for (int j = 0; j < 100; j++) {             if (map[i][j] && map[i+1][j] && map[i][j+1] && map[i+1][j+1]) res++;         }     }     return res; } int main() {       ios_base::sync_with_stdio(0);     cin.tie(0);       cin >> n;     while (n--)     {         int x, y, d, g;         cin >> x >> y >> d >> g;         lines.push_back(D(x, y, d, g));     }       makeGens();       for (D dragon : lines) {         drawLines(dragon);     }       cout << findSqaures() << '\n';     return 0; }