● [파이썬] [구현] 백준 15685 드래곤 커브

문제

https://www.acmicpc.net/problem/15685

15685번: 드래곤 커브

코드

dx=[0,-1,0,1]
dy=[1,0,-1,0]

n=int(input())
array=[list(map(int,input().split())) for _ in range(n)]
# x,y를 방문하면 dp[x][y]=True
dp=[[False]*101 for _ in range(101)]

def draw(r,c,d,g):
    # 시작점 방문
    dp[r][c]=True

    # 0세대 방문
    er,ec=r+dx[d],c+dy[d]
    dp[er][ec]=True

    stack=[]
    stack.append(d)

    for _ in range(g):
        # 이전 세대 이동 복사
        temp=stack
        for i in temp[::-1]:
            # 스택의 top부터 시계 방향으로 90도 회전하여 이동
            er+=dx[(i+1)%4]
            ec+=dy[(i+1)%4]
            dp[er][ec]=True
            stack.append((i+1)%4)

for i in array:
    x,y,d,g=i
    draw(y,x,d,g)

result=0
for i in range(100):
    for j in range(100):
        if dp[i][j]==True and dp[i+1][j]==True and dp[i][j+1]==True and dp[i+1][j+1]==True:
            result+=1
print(result)

어려웠던 부분

드래곤 커브를 구현하는 것이 어려웠다

 

이전세대 이동 방향을 전부 복사한후 전부 90도 회전 시켜 이동

 

stack     temp

1           (1+1)

*) +1은 90도 회전

temp top부터 append

 

stack    temp

1,2       (1+1),(2+1)

 

stack     temp

1,2,3,2  (1+1),(2+1),(3+1)%4,(2+1)