15685: 드래곤 커브 (Python)

<문제 유형> : 규칙 찾기 

- 이 문제의 낯선 점은 도형의 회전과 도형을 만들어가는 과정의 규칙을 찾아 구현하는 것이다.

- 이때 생각해야 하는 것은 도형의 회전을 이 도형을 이루는 선분들의 회전으로 치환하는 것이다. 

   시계 방향으로 90도 회전했을때 방향을 가진 선분들은 다음과 같이 변환된다.

  →  ☞   ↑ 

  ←  ☞   ↓ 

   ↑   ☞  ←

   ↓   ☞  →

- 그리고 다음 세대의 드래곤 커브가 될 때 끝점부터 다시 이어 붙여 선분을 curve 리스트에 차례로 추가하게 되는데, 그림과 같이 0, 1, 2, 3의 순서대로 선분이 추가 된다. 따라서 다음 세대의 선분을 그릴 때 앞선 세대의 드래곤 커브 리스트의 인자를 배열의 마지막 인덱스부터 거꾸로 순으로 이어붙여 만들어 짐을 유의해야 한다. 

<구현해야 하는 것> 

dr_map : (101, 101) 의 크기를 갖는 격자 이중배열, 각 요소에는 드래곤 커브의 꼭짓점의 존재 여부를 저장한다.

              드래곤 커브의 좌표에 해당하면 True, 아니면 False를 담고 있다.

curve: g세대의 드래곤 커브의 선분을 저장하는 리스트  

dragon_curve() : curve 리스트에 담긴 선분을 리스트의 역순의 요소들부터 90도 회전시켜가며 차례로 curve에 추가해 드래곤 커브를 그리는 함수  

 

(1) g에 해당하는 dargon curve 리스트 완성

    : g 만큼 반복문 돌면서 curve리스트에 드래곤 좌표 추가 

(2) 완성된 curve를 참조해 dr_map에 좌표 해당 여부를 저장

(3) 출력 result 연산 

    : (1,1) 크기의 정사각형의 좌표가 모두 드래곤 커브의 좌표에 해당하면 result +1 해줌

---

dr_map = [[False for _ in range(101)] for _ in range(101)]

# right, up, left, down
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

n = int(input())

def dragon_curve(lst):
    for i in range(len(lst)-1,-1, -1):
        d = lst[i]
        d += 1 
        d %= 4

        lst.append(d)

    return lst 

for _ in range(n):
    y, x, d, g = map(int, input().split()) # 문제의 x, y 축을 반대로 입력받아 행 축을 x축, 열 축을 y축으로 함 

    #(1) dragon curve 완성
    curve = []
    curve.append(d) 
    for i in range(1, g+1): 
        curve = dragon_curve(curve)

    #(2) dragon curve를 dr_map에 그리기
    dr_map[x][y] = True
    for dir in curve:
        x += dx[dir]
        y += dy[dir]
        if not dr_map[x][y]:
            dr_map[x][y] = True

#(3)result 출력 
result = 0
for i in range(100):
    for j in range(100):
        if dr_map[i][j] and dr_map[i][j+1] and dr_map[i+1][j] and dr_map[i+1][j+1]:
            result += 1

print(result)