15685_드래곤 커브

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

15685번: 드래곤 커브

 

 

조금 색다른 유형이었는데 푸는 과정이 재밌었던 문제였던 것 같다.

 

우선 결국 지도에 드래곤 커브들을 그려야 하는게 목표였던것 같다.

 

그래서 우선은 회전하는 방법에 대해서 생각을 해보았다.

 

어떤 좌표에서 특정좌표로 회전시키든, 0,0에서 회전시킨다고 생각 하고 다시 옮기면 회전시킨 좌표를 알 수 있다.

 

그런데 좌표의 회전은 결국, x,y좌표를 바꾸고 시계방향이라면 뒤에값에 -1을 곱해주면 구할 수 있음을 깨달았다. 이를 이용해서 회전하는 것을 1단계로 삼았다.

 

그 이후는 드래곤 세대를 늘려나가는거였는데 가장 먼저 든 생각은 재귀였다. 회전시킨 좌표를 원래 가지고 있던 좌표에 더해나가면서 재귀를 통해 그리면 될꺼란 생각이 들었다.

 

마지막에 조금 헤맸는데, 이유는 간단했다. 100까지의 좌표면 입력이 100개가 아닌 101개가 된다는것 이것빼고는 잘 푼듯한 문제였다.

import sys
input = sys.stdin.readline

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

board = [ [0]*101 for _ in range(101)]

def rotate(nodes,cod,cnt,goal):
    main_x,main_y = cod
    new_nodes = []
    if cnt == goal:
        for i in nodes:
            a,b = i
            board[b][a] = 1
        return nodes

    for node in nodes:
        x,y = node
        x -= main_x
        y -= main_y
        x,y = y*(-1),x
        if [x+main_x,y+main_y] not in nodes:
            new_nodes.append([x+main_x,y+main_y])

    return rotate(nodes + new_nodes,new_nodes[0],cnt+1,goal)


def find_square():
    result = 0
    for i in range(100):
        for j in range(100):
            if board[i][j] and board[i+1][j] and board[i][j+1] and board[i+1][j+1]:
                result +=1
    return result

n = int(input())
for _ in range(n):
    x,y,d,g = map(int,input().split())
    rotate([[x,y],[x+dx[d],y+dy[d]]],[x+dx[d],y+dy[d]],0,g)

print(find_square())