15685 - 드래곤 커브

Point 1

0: x좌표가 증가하는 방향 (→)
1: y좌표가 감소하는 방향 (↑)
2: x좌표가 감소하는 방향 (←)
3: y좌표가 증가하는 방향 (↓)

* 일반적으로는 y는 가로로 증가 또는 감소하며, x는 세로로 증가 또는 감소한다. 하지만 이 문제에서는 x가 가로 방향으로 증가 또는 감소하며, y가 세로 방향으로 증가 또는 감소하는 것으로 정의하였다.

 

Point 2

• 0 세대

• 1 세대

• 2세대 

• 3세대

 

위의 그림과 같이 세대별 방향을 보면 이전 세대의 역순 + 1 이라는 규칙성을 발견할 수 있다.

0세대	0
1세대	0 + 1
2세대	0, 1 + 2, 1
3세대	0, 1, 2, 1 + 2, 3, 2, 1

 

from copy import deepcopy

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

N = int(input())
graph = [[0]*101 for _ in range(101)]

for _ in range(N):
    # 일반적인 x와 y 위치가 바뀌어야한다.
    y, x, d, g = map(int, input().split())
    graph[x][y] = 1
    # 누적 방형 좌표가 있는 리스트
    dList = [d]
    # 새롭게 움직이는 좌표만 있는 리스트
    q = [d]
    for _ in range(g+1):
        for k in q:
            x += dx[k]; y += dy[k]
            graph[x][y] = 1
            
        q = list(map(lambda x : (x+1)%4, dList))
        q.reverse()
        dList.extend(q)
            
cnt = 0
for r in range(101):
    for c in range(101):
        if (0<=r+1<101) and (0<=c+1<101):
            if graph[r][c] and graph[r+1][c] and graph[r][c+1] and graph[r+1][c+1]:
                cnt += 1
                
print(cnt)