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

문제

 

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

15685번: 드래곤 커브

 

 

풀이

 

드래곤커브를 회전시켜서 끝점에 붙이기만하면됨.

 

시계방향으로 회전한다는 것은 x, y가 y,-x로 바뀌는 것임. 근데 기준이 원점이 아니므로 원점으로 옮긴 후에 y, -x로 바꾸고 다시 원점으로 이동시킨만큼 더해주어서 회전된 좌표를 구했음.

 

나는 그때그때의 드래곤커브 좌표들을 전부 result라는 배열에 담아서 확인했음.

 

드래곤커브를 회전한 이후에 끝점에 붙여야하는데, 끝점은 시작점을 매 드래곤커브의 끝점을 기준으로 시계방향으로 90도 회전한 좌표가 됨.

예시를 보면 시작점이 (0,0)이고 끝점이 (1,0)임. 이때의 기준은 (1,0)이 됨. 근데 다음 기준은 (1,0)을 기준으로 시작점을 회전시킨 (1,-1)이됨. 다음도 마찬가지로 마지막 끝점인 (1,-1)을 기준으로 시작점을 회전시킨 (0,-2)가됨.

이런식으로 계속해서 기준좌표를 바꿔가며 모든 드래곤커브의 좌표를 하나의 배열에 담고 각각의 칸을 확인하면 결과를 출력할 수 있음.

import sys
input = sys.stdin.readline
board = [[False for _ in range(101)] for _ in range(101)]
result = []
n = int(input())
count = 0
def rotate(base,x,y):
    x -= base[0]
    y -= base[1]
    nx = base[0] + y
    ny = base[1] - x
    if nx < 0 or ny < 0:
        return
    return (nx, ny)
for _ in range(n):
    x, y, d, g = map(int,input().split())
    if d == 0:
        dragon = [(y,x),(y,x+1)]
    elif d == 1 and y >= 1:
        dragon = [(y, x), (y - 1,x)]
    elif d == 2 and x >= 1:
        dragon = [(y, x), (y, x - 1)]
    else:
        dragon = [(y, x), (y + 1,x)]
    base = dragon[-1]
    result += dragon

    for _ in range(g):
        for i in range(len(dragon)):
            new = rotate(base,dragon[i][0],dragon[i][1])
            if new == None:
                continue
            dragon.append(new)
            result.append(new)
        base = rotate(base,y,x)
result = set(result)
for i in range(101):
    for j in range(101):
        if i + 1 < 101 and j + 1 < 101:
            if (i,j) in result and (i + 1, j + 1) in result and (i + 1,j) in result and (i,j + 1) in result:
                count += 1
print(count)