문제
문제에서 “드래곤 커브”라는 새로운 모양을 정의한다. 이 설명에 맞추어 주어진 격자 내에 시작점, 초기방향, 세대를 입력받아 드래곤 커브를 생성한다. 네 귀퉁이가 모두 드래곤 커브의 일부인 격자 칸의 갯수를 구하는 문제이다.
접근
드래곤 커브를 구성하는 점들을 순서대로 저장해 두면 어렵지 않게 풀 수 있다. 문제 설명 그대로 각 점을 마지막 점 기준으로 90도 회전하면 된다. 회전하는 좌표를 식으로 나타내는 것은 그냥 연습장에 좌표평면을 그리면서 찾아도 충분하고, 행렬에 관한 지식이 있다면 다음과 같이 쉽게 유도할 수 있다.
좌표 $(x, y)$인 점을 반시계방향으로 $\theta$ 만큼 회전하면, 회전 변환 행렬은 다음과 같다.
시계방향으로 90도 회전한다면 $\theta = -\pi /2$이므로, 대입한 뒤 $(x,y)$ 벡터를 곱해보면 회전한 지점은 $(-y,x)$임을 쉽게 알 수 있다.
좌표 평면에서 마지막 점 $(r_0,c_0)$에 대해 $(r,c)$점을 90도 시계방향으로 회전한다고 하자. $(r_0,c_0)$가 원점인 좌표계에서 원래 $(r,c)$였던 점은 $(r-r_0,c-c_0)$로 표현된다. 이 점을 시계방향으로 돌리면 $(-c+c_0,r-r_0)$일 것이고, 원점을 다시 처음으로 되돌리면 $(r_0-c+c_0,c_0+r-r_0)$가 된다.
주의할 점
2차원 리스트를 만들 때, 좌표계가 헷갈릴 수 있다. 이 문제는 어차피 네 귀퉁이가 모두 드래곤 커브에 포함되는 칸을 세기 때문에 정답에는 영향을 미치지 않을 것 같다.
격자칸의 유효한 좌표는 0에서 100사이(Inclusive)이므로, 각 격자점은 가로, 세로 101개씩 존재하게 된다.
드래곤 커브를 구성하는 점들을 저장할 때, 순서에 유의하자.
Code
링크# https://www.acmicpc.net/problem/15685
# Implementation
from collections import deque
from sys import stdin
used = [[False for _ in range(101)] for _ in range(101)]
direction = [[0, 1], [-1, 0], [0, -1], [1, 0]]
def make_dragon():
x, y, d, g = map(int, stdin.readline().split())
points = deque()
points.append([y, x])
used[y][x] = True
points.append([y + direction[d][0], x + direction[d][1]])
used[y + direction[d][0]][x + direction[d][1]] = True
while g > 0:
last_r, last_c = points[-1]
for i in reversed(range(len(points) - 1)):
r, c = points[i]
new_r, new_c = last_r + c - last_c, last_c - r + last_r
points.append([new_r, new_c])
if 0 <= new_r <= 100 and 0 <= new_c <= 100:
used[new_r][new_c] = True
g -= 1
return
n = int(stdin.readline().strip())
for _ in range(n):
make_dragon()
ans = 0
for i in range(100):
for j in range(100):
ans += (used[i][j] and used[i][j + 1] and used[i + 1][j] and used[i + 1][j + 1])
print(ans)
