[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만큼 증가한다. 

#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; }