[백준 15685] 드래곤 커브(python)

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

15685번: 드래곤 커브

드래곤 커브 문제

n-1 세대 드래곤 커브의 끝점을 기준으로 90도 시계 방향 회전하여 끝점에 붙여나가 n세대 드래곤 커브를 만들 때, 주어진 시작점과 방향을 고려하여 원하는 세대까지 만들었을 때, 1x1 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 구하는 문제

방법을 찾아 구현하는 문제였다.

📌 문제 접근 포인트

1. 예제를 기준으로 규칙성을 찾기 위해서 드래곤 커브를 구해보자.
0세대 드래곤 커브의 방향은 → 
1세대 드래곤 커브의 방향은 → ↑ (→를 90도로 돌렸으니 ↑)
2세대 드래곤 커브의 방향은 → ↑ ← ↑ (→ ↑를 끝점을 기준으로 생각하면 ↑ → 순서로 90도로 돌아가므로 ← ↑)
3세대 드래곤 커브의 방향은 → ↑ ← ↑ ← ↓ ← ↑ (→ ↑ ← ↑를 끝점을 기준으로 생각하면 ↑ ← ↑ → 순서로 90도로 돌아가므로 ← ↓ ← ↑)
즉 n세대 드래곤 커브는 n-1세대 드래곤 커브에 n-1세대 드래곤 커브를 뒤집어서 각각 90도 돌린 것을 이어 붙인 형태이다.
2. 범위 요구조건이 0 <= x <= 100, 0 <= y <= 100이므로 100칸이 아닌 101칸으로 구성을 해주자. (근데 격자의 크기는 100*100이다 이 생각으로 100으로 만들면 인덱스 에러가 난다)
3. 시작 방향에 대한 요구조건을 맞춰주고, 크기가 1X1이면서 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형을 세어주면 구현 성공

⚙ 내가 푼 정답코드

# 조건 0 : 0세대 드래곤 커브 ㅡ
# 조건 1 : n세대 드래곤 커브 = n-1세대 + n-1세대를 90도
# 조건 2-1 : 생성 규칙 : 0세대 : →  1세대 : → ↑ 2세대 : → ↑(여기서부터 역순으로 뒤집기) ← ↑ 3세대 → ↑ ← ↑(여기서부터 역순으로 뒤집기) ← ↓ ← ↑
# 조건 2-2 : 방향 90도 변환 규칙 : ↑ to ← / ← to ↓ /  ↓ to → / → to ↑ (해당위치 % 4)
# 조건 3 : 시작 방향 고려  
# 조건 4 : 크기가 1x1이면서 네 꼭지점이 모두 드래곤 커브의 일부인 정사각형의 개수  
import sys
N = int(sys.stdin.readline())
dy = [1, 0, -1, 0]
dx = [0, -1, 0, 1]
board = [[0]*101 for _ in range(101)]
for _ in range(N):
    y, x, d, g = map(int, sys.stdin.readline().split())
    board[y][x] = 1 # 시작 위치 
    curve = [d] # 조건 3 시작 방향 입력

    for _ in range(g):
        for i in range(len(curve)-1, -1, -1): # 조건 0 ~ 2-1 역순으로 90도 뒤집기 시작해야하니
            curve.append((curve[i]+1) % 4) # 조건 2-2


    for i in range(len(curve)): # 커브 방향 동안
        y, x = y + dy[curve[i]], x + dx[curve[i]]
        board[y][x] = 1

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]: # 조건 4
            result += 1
print(result)