문제
풀이
드래곤 커브의 방향은 0 (동쪽), 1 (북쪽), 2 (서쪽), 3 (남쪽) 이다. 그리고 드래곤 커브는 일정한 규칙을 갖는다.
- 0세대 : 0
- 1세대 : 0 1
- 2세대 : 0 1 2 1
- 3세대 : 0 1 2 1 2 3 2 1
1세대와 2세대를 살펴보자.
1세대는 ‘0 1’ 이고 2세대는 ‘0 1’ 에 ‘2 1’ 이 붙는다.
‘2 1’ 은 ‘0 1’을 뒤집은 후 1을 추가한 형태이다.
마찬가지로 2세대와 3세대를 살펴보면, 3세대는 2세대 ‘0 1 2 1’ 에 이것을 뒤집고(‘1 2 1 0’) 1을 더한 ‘2 3 2 1’을 추가한 형태이다.
그리고 여기서 주의할 점은 4세대로 넘어가게 되면 4라는 숫자가 나오게 되는데 이는 0을 의미한다.
즉 (i + 1) % 4 의 형태로 계산해주면 된다.
이러한 규칙을 활용해 드래곤 커브를 그려주고 모든 꼭지점이 드래곤커브인 정사각형의 개수를 세면 된다.
이제 소스 코드를 살펴보자.
소스 코드
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
#include <iostream>
#include <vector>
using namespace std;
int n, x, y, d, g;
int map[101][101];
int dy[4] = {0, -1, 0, 1};
int dx[4] = {1, 0, -1, 0};
int cnt;
vector<int> dir_info; // 드래곤커브의 방향정보를 저장하는 vector
void makeDragonCurve()
{
int size = dir_info.size();
for (int i = size - 1; i >= 0; i--)
{
int nd = (dir_info[i] + 1) % 4;
y += dy[nd];
x += dx[nd];
map[y][x] = 1;
dir_info.push_back(nd);
}
}
// 모든 꼭지점이 드래곤커브인 정사각형 개수 세기
void countSquare()
{
for (int i = 0; i < 101; i++)
{
for (int j = 0; j < 101; j++)
{
if (map[i][j] == 1 && map[i][j + 1] == 1 && map[i + 1][j] == 1 && map[i + 1][j + 1] == 1)
cnt++;
}
}
}
void solve()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
while (n--)
{
cin >> x >> y >> d >> g;
dir_info.clear();
// 0세대 드래곤커브 그리기
map[y][x] = 1;
y += dy[d];
x += dx[d];
map[y][x] = 1;
dir_info.push_back(d);
// g 세대의 드래곤커브 그리기
while (g--)
{
makeDragonCurve();
}
}
countSquare();
cout << cnt << '\n';
}
int main()
{
solve();
return 0;
}
