[백준 문제풀이] 15685번 드래곤 커브

파이썬을 이용하여 다시 풀어본 드래곤 커브 문제이다.

18년도 삼성전자 코딩 테스트에 기출되었던 문제이고, 보통은 스택을 이용하여 푸는 방식이 일반적인 것 같다.

일전에 풀었을 때는 미리 드래곤 커브를 모두 만들어 놓는 방식으로 만들려고 했다.

드래곤 커브에서는 end 기준으로 90도 회전하도록 되어 있어 아래와 같은 수도코드를 이용하여
최대 generation인 10에 맞추어 모든 행렬을 사전에 만들어 놓고 주어진 수에 합성하는 방식으로 짰었다.

거기다가 C로 짜니 코딩하는 시간이 많이 걸릴 수밖에...

ARR1 = find end point and transition to [end_x, end_y] = 0


for all point:
    ARR2[nx; ny] = [cos sin; -sin -cos]*[x; y]

DRAGONCURVE(G)  = ARR1 + ARR2

save DRAGONCURVE(G)

이후 주어진요청에 따라 방향 회전 후 평면 이동하여 합성
(값이 짤릴 수 있으므로 배열의 길이는 200)

예전에는 코딩 테스트를 별로 준비해야한다는 생각이 없어서 구현 문제인 줄알고 풀었는데
코딩 테스트를 준비하면서 다른 풀이들을 살펴 보니 모두가 스택으로 풀고 있었다..

스택으로 코딩을 해보니 정말 쉽게 풀리는...

스택으로 풀이한 코드는 아래와 같다.

MAX_N = 20+1
MAX_XY = 100+1
MAX_G = 10+1
MAX_D = 3+1  # R U L D
d_curve = []

dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]

# 1 <= N <= 20
# 0 <= x,y <= 100
# 0 <= d <= 3
# 0 <= g <= 10

import copy
def make_dcurve():
    gen0 = [0]
    d_curve.append(gen0)
    for i in range(1, MAX_G):
        prev = copy.deepcopy(d_curve[i-1])
        curr = prev
        for d in prev[::-1]:
            d = (d+1) % MAX_D
            curr.append(d)
        d_curve.append(curr)


n = int(input())
#print(n)

make_dcurve()

a = [[0]*(MAX_XY+1) for _ in range(MAX_XY+1)]
for i in range(n):
    x, y, d, g = map(int, input().split())
    #print(x,y,d,g)
    tmp = list(map(lambda x: (x+d) % MAX_D, d_curve[g]))
    a[y][x] = 1
    for j in tmp:
        x = x+dx[j]
        y = y+dy[j]
        if 0 <= x < MAX_XY and 0 <= y < MAX_XY:
            a[y][x] = 1

answer = 0
for x in range(MAX_XY):
    for y in range(MAX_XY):
        if a[y][x] and a[y][x+1] and a[y+1][x] and a[y+1][x+1]:
            answer += 1


print(answer)

... 쉽게 풀리네

역시 코딩 테스트는 핵심 아이디어 캐치가 중요한 듯 하다.