[백준] 15685번 - 드래곤 커브 (파이썬)

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

# 드래곤 커브
import sys
input = sys.stdin.readline
T = int(input())
arr = [[False] * 101 for _ in range(101)]
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

q = []
for _ in range(T):
    y, x, d, g = map(int, input().split())
    q.append((x, y, d, g))


def dragon_curve():
    for x, y, d, g in q:
        arr[x][y] = True
        dir = [d]
        for _ in range(g):
            for d in range(len(dir)-1, -1, -1):
                temp = (dir[d] + 1) % 4
                dir.append(temp)
        for d in dir:
            x += dx[d]
            y += dy[d]
            if 0 <= x < 101 and 0 <= y < 101:
                arr[x][y] = True


dragon_curve()

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

 

구현

1. 입력을 받고 q에 append한다

2. dragon_curve 함수 실행

    - arr[x][y]를 True로 해주고

    - q를 돌면서 d와 g에 따른 이동 경로 dir을 update해준다

    - 나온 이동경로(dir)을 x와 y에 더해주면서 범위 내라면 이동(arr[x][y]=True)

3. 전체 arr을 확인하면서 4개의 꼭지점이 True이면 result +=1

4. result 출력

 

dir에 들어갈 내용의 규칙을 찾는게 중요하다

추가된 요소를 보면 기존의 리스트를 reverse하고 +1을 한 값을 추가해준 것과 같다

• 방향은 0, 세대는 3 일경우
• dir = 0
• dir = 0 1
• dir = 0 1 2 1
• dir = 0 1 2 1 2 3 2 1