[BOJ] 15685 - 드래곤 커브

초기 설정

격자와 방향(방향은 문제에서 주어진 순서대로 담는다)
격자는 선이 아닌 점을 보므로 101 * 101, 방향은 튜플(x방향, y방향)

grid = [[0] * 101 for  _ in range(101)]
direction = [(1,0), (0,-1), (-1,0), (0,1)]

0세대 드래곤 커브를 먼저 설정해준다
이후, g값(세대 값)이 0이 아닌 이상 g값만큼 dc_move()함수를 실행해준다
dc는 드래곤 커브를 구성하는 좌표값을 담은 리스트이고 순서대로 담는다
하나의 드래곤 커브가 만들어질 때마다 격자를 채운다(1: 드래콘 커브가 지나간 좌표)

for _ in range(dc_num):
    #입력값 저장 및 타입 변환
    dc_info = input().strip().split(' ')
    for i in range(len(dc_info)):
        dc_info[i] = int(dc_info[i])
    
    #0세대 드래곤 커브 설정
    dc = [(dc_info[0], dc_info[1]), (dc_info[0]+direction[dc_info[2]][0], dc_info[1]+direction[dc_info[2]][1])]
    #드래곤 커브
    if dc_info[3] != 0:
        for _ in range(dc_info[3]):
            dc = dc_move(dc)

    #격자 채우기
    for i in dc:
        if 101 > i[0] >= 0 and 101 > i[1] >= 0 and grid[i[1]][i[0]] == 0: 
            grid[i[1]][i[0]] = 1
        else:
            pass

드래곤 커브가 돌아가는 방식

모든 좌표를 다같이 돌릴려고 했었는데 생각해보니 거리나 방향에 따라서 좌표값이 제각각이라 일정한 패턴을 찾기가 어렵다고 판단 → 실제로 돌리는 방법에서 패턴을 찾아야겠다고 판단

중심을 기준으로 돌아가는건 중심과 가장 가까운 좌표와, 중심이 아닌 좌표들 중 서로 가장 가까운 좌표끼리의 차이(중심 좌표를 포함하지 않는 드래곤 커브의 변)

가장 가까운 좌표끼리의 차이는 일정하게 돌아가는 패턴이 있으며, 돌렸을 때 좌표값을 직접 구할 필요가 없는 장점이 있다

돌린 후의 차이값은 파악이 되니까 중심과 가장 가까운 좌표값만 실제로 돌리고 나머지는 변화된 차이값만 따라가면서 좌표값을 구하면 된다

검은 화살표(돌리기 전 차이), 빨간색 화살표(돌린 후 차이)

상단의 그림에 표현된 좌표를 돌리는 패턴 구현
이는 좌표를 돌리거나 좌표값 차이를 돌릴 때나 같은 패턴이 작용한다

def spin(d):
    if d[1] != 0:
        return (-d[1], d[0])
    else:
        return (d[1], d[0])

spinned라는 중심 좌표와 가장 가깝고 돌아간 좌표를 먼저 구해주고(돌린 차이가 적용될 출발점) 이전 세대의 드래곤 커브에서 나머지 좌표들의 차이를 구하고 돌려준다

spinned 값은 new_coord_array에 들어가 변화된 좌표의 처음을 표시해준다
이후 new_coord_array의 가장 마지막 좌표에 돌아간 차이를 적용해주며 new_coord를 append 해준다

한 세대의 드래곤 커브가 만들어질 때마다 new_coord_array를 dc에 합쳐준다

def dc_move(n):
		#좌표값의 차이 구하기 및 돌리기
    dif = ((n[-2][0] - n[-1][0]), (n[-2][1] - n[-1][1]))
    spin_dif = spin(dif)
    spinned = ((n[-1][0] + spin_dif[0]), (n[-1][1] + spin_dif[1]))

    if len(n) >= 3:
        new_coord_array = [spinned]
        for i in range(len(n)-3,-1,-1):
            dif = ((n[i][0] - n[i+1][0]), (n[i][1] - n[i+1][1]))
            spin_dif = spin(dif)
            new_coord = ((new_coord_array[-1][0] + spin_dif[0]), (new_coord_array[-1][1] + spin_dif[1]))
            new_coord_array.append(new_coord)

        n += new_coord_array

    else:
        n.append(spinned)

    return n

grid가 완성이 됐으면 좌표 101개중 100x100만 돌면서 각자 위치를 기준으로 1x1만큼 탐색해준다
4개의 좌표값의 합이 4인 경우(사각형이 만들어짐) 사각형의 갯수를 늘려나간다

# 사각형 갯수 세기
num = 0
for i in range(100):
    for s in range(100):
        check = grid[i][s] + grid[i+1][s] + grid[i][s+1] + grid[i+1][s+1]
        if check == 4:
            num += 1

print(num)

보완할 점

좌표끼리의 차이를 구할 때, for 문을 돌릴수록 이미 구한 차이지만 누적해서 차이를 구하고 있다. 시간 초과 나면 고쳐야지,,, 했지만 다행히 통과됐다ㅎㅎ 이 부분은 추후에 리팩토링 해봐야 할 것 같다