백준 15685 : 드래곤 커브(파이썬)

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

15685번: 드래곤 커브

 

문제는 위와 같다.

초기조건을 잘못주는 바람에 한참 해맸다... 앞으로 조심해야겠다.

드래곤 커브를 그릴때 보드판 크기는 0 보다 크거나 같고, 100보다 작거나 같다.

그러므로,, 보드판 지정할 때 [[False] * 101 for _ in range(101)] 이렇게 지정해줘야한다.

덕분에 스스로 설정해둔 제한 시간(180분) 안에 못풀었다.. 이런 실수는 없도록 하자.

아무튼 해당 문제의 핵심은 커브를 그리는 방법에 있다.

 

 1. 커브를 어떻게 그릴 것인가?

이리 봐도, 저리 봐도 세대별 규칙성은 보이지 않는다. 수학적인 접근을 하면 쉽게 만들 수 있다.

바로 끝점을 (0, 0)으로 고정한 상태에서 90도 시계방향으로 돌리는 것이다. 따라서, 끝점을 기준으로 좌표변환을 실시하면 세대를 거칠 때마다 커브를 그릴 수 있다.

매 세대 계산시 끝점을 (0, 0) 으로 주고, 좌표변환 실시한 뒤 원래 좌표로 평행이동 하면 커브를 그릴 수 있다. 코드는 다음과 같다.

def gen_curve(arr) :
    # End Point (0, 0) 으로 만들어주자
    # print(arr)
    # x, y 좌표 기준
    ex, ey = arr[-1][0], arr[-1][1]
    # print(ex, ey)
    for i in range(len(arr)) :
        arr[i][0] -= ex
        arr[i][1] -= ey
    # print(arr)
    # 좌표 변환 해주자 90도 만큼 시계방향 전환
    # 끝 점은 계산 안함
    # print(arr, len(arr))
    for i in range(len(arr) - 2, -1, -1) :
        # print(i, arr[i][0], arr[i][1])
        nx = coord[0][0] * arr[i][0] + coord[0][1] * arr[i][1]
        ny = coord[1][0] * arr[i][0] + coord[1][1] * arr[i][1]
        arr.append([nx, ny])
    # 이제 ex 만큼 다시 더해줘서 원상 복귀
    for i in range(len(arr)) :
        arr[i][0] += ex
        arr[i][1] += ey
    return arr

 2. 주의사항

 좌표 계산은 문제에서 정의된 것과 같이 2차원 좌표계를 활용하게 된다. 그러나 보드판에 그릴때는 인덱스가 뒤바뀌게 되므로, 주의가 필요하다. x좌표는 보드의 두 번째 요소에 들어가고, y좌표는 첫 번째 요소에 들어가게 된다.

 그리고 0세대일 때의 최초 좌표는 초기값으로 입력하고, 입력 값이 0세대에서 계산이 끝날 경우에는 커브 생성을 건너뛰도록 하였다. 

for i in range(len(info_c)) :
    q = []
    # 0세대 좌표 값 입력 x, y
    q.append([info_c[i][0], info_c[i][1]])
    q.append([info_c[i][0] + dx[info_c[i][2]], info_c[i][1] + dy[info_c[i][2]]])
    if info_c[i][3] > 0 :
        for j in range(info_c[i][3]) :
            # 세대 만큼 반복 진행
            q = gen_curve(q)
    # print(i, q)
    # 이제 1로 채워주자
    for k in range(len(q)) :
        # board 좌표 인덱스는 서로 바꿔줘야함
        by = q[k][0]
        bx = q[k][1]
        if bx >= 0 and bx < 101 and by >= 0 and by < 101 :
            board[bx][by] = True
        else :
            continue

 3. 전체 코드

 메모리 125696kb / 시간 132 ms

 마지막으로 정사각형 세는 부분은 각 Cell의 Center 값을 기준으로 4개의 좌표를 만들어 확인하도록 했다. 더 좋은 아이디어가 생기면 업데이트 할 예정.

n = int(input())
# Curve Info : x, y, d, g
info_c = [list(map(int, input().split())) for _ in range(n)]
board = [[False] * 101 for _ in range(101)]
# 좌표 변환식
coord = [[0, -1], [1, 0]]
# print(coord[0][0])
# 방향 좌표
# 우, 상, 좌, 하
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]

def gen_curve(arr) :
    # End Point (0, 0) 으로 만들어주자
    # print(arr)
    # x, y 좌표 기준
    ex, ey = arr[-1][0], arr[-1][1]
    # print(ex, ey)
    for i in range(len(arr)) :
        arr[i][0] -= ex
        arr[i][1] -= ey
    # print(arr)
    # 좌표 변환 해주자 90도 만큼 시계방향 전환
    # 끝 점은 계산 안함
    # print(arr, len(arr))
    for i in range(len(arr) - 2, -1, -1) :
        # print(i, arr[i][0], arr[i][1])
        nx = coord[0][0] * arr[i][0] + coord[0][1] * arr[i][1]
        ny = coord[1][0] * arr[i][0] + coord[1][1] * arr[i][1]
        arr.append([nx, ny])
    # 이제 ex 만큼 다시 더해줘서 원상 복귀
    for i in range(len(arr)) :
        arr[i][0] += ex
        arr[i][1] += ey
    return arr

for i in range(len(info_c)) :
    q = []
    # 0세대 좌표 값 입력 x, y
    q.append([info_c[i][0], info_c[i][1]])
    q.append([info_c[i][0] + dx[info_c[i][2]], info_c[i][1] + dy[info_c[i][2]]])
    if info_c[i][3] > 0 :
        for j in range(info_c[i][3]) :
            # 세대 만큼 반복 진행
            q = gen_curve(q)
    # print(i, q)
    # 이제 1로 채워주자
    for k in range(len(q)) :
        # board 좌표 인덱스는 서로 바꿔줘야함
        by = q[k][0]
        bx = q[k][1]
        if bx >= 0 and bx < 101 and by >= 0 and by < 101 :
            board[bx][by] = True
        else :
            continue

# 이제 정사각형 개수 세자... 1x1임
result = 0
for i in range(100) :
    for j in range(100) :
        x = 0.5 + i
        y = 0.5 + j
        # print(x, y)
        x1, y1 = int(x - 0.5), int(y - 0.5)
        x2, y2 = int(x + 0.5), int(y - 0.5)
        x3, y3 = int(x + 0.5), int(y + 0.5)
        x4, y4 = int(x - 0.5), int(y + 0.5)

        if board[y1][x1] and board[y2][x2] and board[y3][x3] and board[y4][x4] :
            # print(y1, x1, y2, x2, y3, x3, y4, x4)
            result += 1

print(result)