문제 링크
https://www.acmicpc.net/problem/15685
🕒 Python 풀이시간: 60분
dx=[0,-1,0,1]
dy=[1,0,-1,0]
def make_dragon_curv(deep,generation):
global dragon_curvs
if deep==generation:
return
# print(deep)
px,py=-1,-1
pre_dir=-1
for i in range(len(dragon_curvs)-1,-1,-1):
dir=dragon_curvs[i][2]
if len(dragon_curvs)-1==i:
nx,ny=dragon_curvs[i][0]+dx[dir],dragon_curvs[i][1]+dy[dir]
else:
nx,ny=px+dx[pre_dir],py+dy[pre_dir]
px,py=nx,ny
pre_dir=(dir+1)%4
if nx<0 or ny<0 or nx>=101 or ny>=101:
return
dragon_curvs.append((nx,ny,(dir+1)%4))
make_dragon_curv(deep+1,generation)
answer=0
board=[[0]*101 for _ in range(101)]
n=int(input())
for i in range(n):
x,y,d,g=map(int,input().split())
dragon_curvs=[(y,x,d)]
make_dragon_curv(0,g)
for x,y,d in dragon_curvs:
board[x][y]=1
board[dragon_curvs[-1][0]+dx[dragon_curvs[-1][2]]][dragon_curvs[-1][1]+dy[dragon_curvs[-1][2]]]=1
for i in range(0,100):
for j in range(0,100):
if board[i][j]==1 and board[i+1][j]==1 and board[i][j+1]==1 and board[i+1][j+1]==1:
answer+=1
print(answer)🐉 드래곤 커브 생성 및 사각형 찾기 🔍
드래곤 커브라는 세대가 지날 때마다 현재 선들의 위치와 방향을 기준으로 새로운 선을 그리는 문제이다. 현재의 선들이 그려져 있고 방향이 있을 때 이 선들이 마지막 점을 기준으로 시계방향으로 90도 회전되서 그려진다.
세대가 지날 때마다 현재의 선을 기준으로 다시 그리기 때문에 재귀를 통해 접근하려고 하였다. 드래곤 커브 자체를 시작점과 방향으로 이루어진 선분으로 저장을 하였기 때문에 세대가 지날 때 모든 전의 선분을 거꾸로 순환하였지만 처음 선분만 다르게 처리하였다. 거꾸로 모든 지난 세대 선분을 순회한 이유는 시계방향으로 90도 회전될 시에 시작점이 저번 세대의 끝점이 되기 때문이다.
세대가 시작될 때, 시작점을 찾기 위해서는 저번 세대 마지막 선분의 시작 점에서 끝점으로 이동시켜서 시작점을 구해낸다. 이 다음부터는 각 선분의 방향을 기준으로 방향을 구하고 각 선분의 시작점은 저번 선분의 끝점을 기준으로 한다. 그렇게 각 세대를 통해 드래곤 커브를 완성시킨다.
각 완성된 드래곤 커브를 빈 101*101 칸에 반영하여 점을 찍어준다. 이때, 시작점과 방향으로만 저장했기 때문에 마지막 점은 따로 찍어줘야 한다. 모든 점을 찍은 후 board를 순회하면서 4개의 붙어있는 점이 사각형을 이루고 있는 경우의 수를 구하면 된다.
이렇게 Python로 백준의 "드래곤 커브" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
