[백준] 15685번 : 드래곤 커브

해당 문제는 구현문제로 n+1 세대의 드래곤의 커브는 n드래곤커브를 회전시킨뒤 확장하는 구현을 해야합니다.

또한 정사각형의 네 꼭지점이 모두 드래곤 커브의 일부인 것의 개수를 카운팅 하는것을 구현해야한다.

1. n세대의 드래곤 커브 만들기
   1. 드래곤 커브를 만들때 만드는 과정을 저장해야한다.
   2. 시작점이 0,0 이고, 방향이 0인 0세대의 드래곤 커브는 (0, 0), (0,1) 이다.
   3. 그다음 1세대 드래곤 커브는 0세대의 드래곤커브를 복사, 90도 회전시킨뒤 기존에 있던 0세대의 드래곤커브에 추가한다.
   90도를 회전시킬때에는 기존에 있던 n-1 세대의 드래곤커브의 방문 큐값을 시계방향으로 회전시킨다
2. 정사각형 네 꼭지점이 모두 드래곤 커브의 일부인것의 개수를 카운팅한다.
   1. 특정 점으로부터 (1,0) (0,1), (1,1) 의 값이 모두 같다면 네 꼭지점이 모두 정사각형 임으로 정사각형의 개수를 카운팅해준다.

MAX_SIZE = int(101)
from copy import deepcopy
from pprint import pprint
move = [(0,1), (-1,0), (0,-1), (1,0)]
move2 = [(0,1), (1,0), (1,1)]
N = int(input())
table = [[0 for _ in range(MAX_SIZE)] for _ in range(MAX_SIZE)]

def getsqure():
    cnt = 0
    for i in range(MAX_SIZE):
        for j in range(MAX_SIZE):
            if table[i][j]:
                squere = [False for _ in range(3)]
                for k in range(len(move2)):
                    ny = move2[k][0] + i
                    nx = move2[k][1] + j
                    if MAX_SIZE > ny >=0 and MAX_SIZE > nx >= 0 and table[ny][nx]:
                        squere[k] = True

                if all(squere):
                    cnt += 1

    return cnt

def rotate(idx):
    if idx == 3:
        return move[0]
    else:
        return move[idx+1]
def dragon(i,j, queue, depth):
    if depth == g: # 드래곤 세대 까지만 탐색
        return queue

    newqueue = []
    temp = reversed(queue)
    for m in temp: # 기존에 그렸던 것을 회전하여 생성한다.
        newqueue.append(rotate(move.index(m)))

    # 좌표를 움직인다.
    for ny, nx in newqueue:
        i = ny + i
        j = nx + j

    return dragon(i,j, deepcopy(queue+newqueue), depth+1)

visitqueue = []
for _ in range(N):
    x, y, d, g = map(int, input().split())
    ny = y + move[d][0]
    nx = x + move[d][1]
    queue = dragon(ny, nx, [move[d]], 0)

    starty = y
    startx = x
    table[y][x] = 1
    for ny, nx in queue:
        starty = ny + starty
        startx = nx + startx
        table[starty][startx] = 1

print(getsqure())