문제 링크

15685 - 드래곤커브

문제 설명

드래곤 커브는 (시작점, 시작방향, 세대) 세 가지 속성으로 이루어지고, 이차원 좌표평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다.

0세대 드래곤 커브

(0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브

1세대 드래곤 커브
-> 0세대 드래곤 커브를 1. 끝점기준으로 시계방향 90도 회전 2. 0세대 드래곤 커브의 끝점에 붙힘

이때 끝점은 시작점에서 선분을 타고 이동했을때 제일 먼 거리에 있는 점을 의미한다.

2세대, 3세대 드래곤 커브는 다음과 같다.

즉, K(K > 1)세대 드래곤 커브는 K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시킨 다음, 그것을 끝 점에 붙인 것이다.

크기가 100×100인 격자 위에 드래곤 커브가 N개 있을때, 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수를 구하라 (0 ≤ x ≤ 100, 0 ≤ y ≤ 100)

문제 풀이

정말.. 이해부터 어려운 문제였음 ㅠ

일단 N세대는 N-1세대를 1. 끝점기준 90도 회전 2. 끝점에 붙히기
N세대가 N-1세대를 포함하므로 일종의 dp개념을 이용하면 메모리도 시간도 아낄 수 있을거라고 생각했다.
각 커브에 대해서,

• dp[i] : i번째 세대의 중복되지 않는 드래곤 커브 좌표
• end[i] : i번째 세대의 끝점

을 저장한다.
2세대를 예로들면, dp[2] = [(0,-1), (0, -2)], end[2] = (0,-2)라고 할 수 있다.

dp[0], end[0]을 주어진 입력대로 초기화하고, 재귀를 돌며 n번째 드래곤 커브의 좌표를 구하는 dragon_curve()를 호출한다.
까지의 코드가 이만큼

# dp[i] : 시작좌표 (x,y)기준 j번째 세대
    dp = [[] for _ in range(20)]
    end = [[] for _ in range(20)]

    dp[0] = [(c[0], c[1]), (c[0]+dx[c[2]], c[1]+dy[c[2]])]
    end[0] = [c[0]+dx[c[2]], c[1]+dy[c[2]]]
    dragon_curve(c[3]) #n번째까지 드래곤커브의 좌표 구하기

dragon_curve(n)는 재귀를 이용해서 dp[n]을 구한다.

def dragon_curve(n):
    if dp[n]:
        return dp[n]
    else:
        # dp로 드래곤커브 좌표 구하기
        dp[n] = rotate(dragon_curve(n-1), end[n-1][0], end[n-1][1], n)

rotate()는 이 문제의 핵심이라고 할 수 있는 끝점 기준 90도 회전을 구현한 함수이다. 그림 그려서 한참 생각함 ㅠ

(0,0)에서 시작한 3세대 드래곤 커브를 봤을때, 얘는 2세대의 끝점인 (0,-2)를 기준으로 90도 회전해서 (0,-2)에 갖다 붙힌 모습이다.
(a, b)를 끝점 (x,y)를 기준으로 시계방향 90도 회전한 결과가 (a', b')라고 하면,

dx = x-a, dy = y-b
a' = x+dy, b' = y-dx

의 규칙을 찾을 수 있다. (이해가 안된다면 그림을 그려보는 수밖에 .,,)

위의 규칙을 바탕으로 끝점 제외 N-1세대의 드래곤커브의 모든 점을 90도 회전하고 이를 dp[N]에 넣어주면 끝임 ㅋ.ㅋ,,

def rotate(pre, x, y, n):
    # 기준점 x, y 기준으로 curve의 모든 좌표 회전시키기
    new_g = []
    rotation = []
    for i in range(n):
        rotation += dp[i]

    for a,b in rotation:
        if (a, b) != (x, y):
            d_x, d_y = x-a, y-b
            n_x, n_y = x+d_y, y-d_x
            new_g.append((n_x, n_y))
            if (a, b) == (c[0], c[1]): #끝점 갱신
                end[n] = [n_x, n_y]
    return new_g

첨에 끝점을 선분따라 제일 먼 점이 아닌 그냥 유클리디안,, 으로 계산해서 한참 헤맸는데 어떤 경우던 끝점은 90도 회전된 시작점이다. ㅋ.ㅋ,,,,,

그리고 하나 더 주의해야될 점,, 보드가 100*100라고 나와있지만 0 ≤ x ≤ 100, 0 ≤ y ≤ 100이기 때문에 for문 돌면서 체크할때 인덱스 100번까지 확인해줘야 한다. 어떻게 아냐구요? index error에 눈물흘렸기 때문에,,

아무튼 전체 코드는 다음과 같다

import sys
import math

input = sys.stdin.readline

N = int(input())
board = [[0]*101 for _ in range(101)]
curves = []
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
for i in range(N):
    curves.append(list(map(int, input().split())))

def rotate(pre, x, y, n):
    # 기준점 x, y 기준으로 curve의 모든 좌표 회전시키기
    new_g = []
    rotation = []
    for i in range(n):
        rotation += dp[i]

    for a,b in rotation:
        if (a, b) != (x, y):
            d_x, d_y = x-a, y-b
            n_x, n_y = x+d_y, y-d_x
            new_g.append((n_x, n_y))
            if (a, b) == (c[0], c[1]):
                end[n] = [n_x, n_y]
    return new_g

def dragon_curve(n):
    if dp[n]:
        return dp[n]
    else:
        # dp로 드래곤커브 좌표 구하기
        dp[n] = rotate(dragon_curve(n-1), end[n-1][0], end[n-1][1], n)

for c in curves:
    # dp[i] : 시작좌표 (x,y)기준 j번째 세대
    dp = [[] for _ in range(20)]
    end = [[] for _ in range(20)]

    dp[0] = [(c[0], c[1]), (c[0]+dx[c[2]], c[1]+dy[c[2]])]
    end[0] = [c[0]+dx[c[2]], c[1]+dy[c[2]]]
    dragon_curve(c[3]) #n번째까지 드래곤커브의 좌표 구하기

    for i in range(len(dp)):
        if not dp[i]:
            break
        else:
            # 드래곤 커브 표시하기
            for d in dp[i]:
                board[d[1]][d[0]] = 1
                
answer = 0
for i in range(100):
    for j in range(100):
        if board[i][j] == 1 and board[i][j+1] == 1 and board[i+1][j] == 1 and board[i+1][j+1] == 1:
            answer += 1

print(answer)

1일 1알골 하고싶은데 쉽지 않구만요..