문제
접근
문제를 부분 문제로 쪼개서 생각하면 쉬워진다.
우선 드래곤 커브를 그릴 줄 알아야 한다.
현재 주어진 좌표 중 마지막 좌표를 기준으로 회전한다.
그럼 한 세대를 거칠 때마다 마지막 좌표는 어떻게 바뀔까?
마지막 좌표를 기준으로 회전하니, 회전이 끝나면 마지막좌표는 항상 최초좌표가 회전한 좌표가 될 것이다.
예를 들어 0세대 좌표 목록이 다음과 같다고 하자.
[c1, c2]
그럼 c2를 기준으로 회전하게 된다.
c2는 중심점이 되므로 회전해도 똑같다.
c1을 회전한 결과는 c3가 되고 좌표목록은 이렇게 업데이트 될 것이다.
[c1, c2, c3]
그럼 시작점은 이제 c3이다.
c3는 마찬가지로 자기자신이며, c2를 회전하여 c4가 나오고 c1을 회전하여 c5가 나온다.
[c1, c2, c3, c4, c5]
항상 마지막 좌표는 배열의 마지막 원소가 된다.
이를 유지하기 위해서는 회전 후 좌표를 얻을 때 배열을 뒤에서부터 연산하며 업데이트해야 한다.
위에서 한 세대를 더 진화한다고 하면 c5부터 순서대로 연산하고 붙여넣어야 하는 것이다.
그럼 회전은 어떻게 할까?
항상 시계방향으로 90도 라고 했으니
회전 행렬은 다음과 같다.
[cos90 sin90]
[-sin90 cos90]
나는 수학 빠가라서 좌표를 자유자제로 가지고 놀줄 모른다.
그래서 회전 중심축을 항상 0,0으로 맞춰줘야겠다.
현재 주어진 좌표 배열을 중심좌표를 기준으로 삼아 평행이동 시킨다.
중심좌표가 x, y라면 모든 좌표들에 -x,-y를 해주면 된다.
이제 회전할 준비가 끝났다.
위의 회전 행렬을 좌표들에 각각 곱하여 회전 후 좌표를 얻는다.
이제 아까 평행이동한걸 다시 돌려줘야 한다.
회전 후 좌표에 다시 +x, +y를 해준다.
아 그리고 이 문제의 좌표계는 y가 거꾸로 되있다.
이거는 처음 입력받고 나서 그냥 -y로 해줬다.
결과가 y축으로 대칭이 되겠지만 상관없다.
우린 완성된 사각형의 개수만 알면되니까
이제 set을 한번 거쳐서 중복된 좌표를 다 없애주자.
이제 드래곤 커브를 다 그렸다.
사각형의 개수는 어떻게 구할까?
주어지는 인풋들의 크기가 그렇게 크진 않아서 그냥 n^2으로 계산했다.
사각형을 이루는 조건을 고정해주면 같은 사각형을 여러번 세는 일은 발생하지 않는다.
난 현재 좌표가 사각형의 좌측상단 꼭지점인 경우에 대해서만 연산을 했다.
드래곤 커브의 모든 좌표를 돌면서 현재 좌표를 기준으로 우상, 우하, 좌하 세개의 좌표가 존재하는지 확인하면 된다.
코드
- 파이썬 코드
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
import sys
input = sys.stdin.readline
ROTATION_MATRIC = ((0,1),(-1,0))
def drawDragonCurve(x, y, direction, gen, dotSet):
dx = [1,0,-1,0]
dy = [0,1,0,-1]
y = -y
lx = x + dx[direction]
ly = y + dy[direction]
dotList = [(x, y), (lx, ly)]
for i in range(gen):
lx = dotList[-1][0]
ly = dotList[-1][1]
tmp = []
for j in range(1,len(dotList)+1):
# 평행 이동
nx = dotList[-j][0] - lx
ny = dotList[-j][1] - ly
# 회전 이동
rx = ROTATION_MATRIC[0][0]*nx + ROTATION_MATRIC[0][1]*ny
ry = ROTATION_MATRIC[1][0]*nx + ROTATION_MATRIC[1][1]*ny
# 평행 이동
nx = rx + lx
ny = ry + ly
tmp.append((nx, ny))
dotList = dotList + tmp
dotSet.update(dotList)
if __name__ == "__main__":
n = int(input())
dotSet = set()
for _ in range(n):
x, y, direction, gen = map(int, input().split())
drawDragonCurve(x, y, direction, gen, dotSet)
dotList = list(dotSet)
ans = 0
for x, y in dotList:
if (x+1, y) in dotList and (x, y-1) in dotList and (x+1, y-1) in dotList:
ans += 1
print(ans)