[백준] 15685번: 드래곤 커브(골드3, 파이썬)

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

15685번: 드래곤 커브

 

아이디어

드래곤 커브 방향의 규칙성을 찾고 구현하여 풀었다. (1시간 40분 정도 걸렸다.....)

 

4 2 1 3 이라는 입력이 들어왔을 때를 예로 들면,

g = 0 일 때, (4,2) 에서 1 방향으로 이동한다.

g = 1 일 때, (4,1) 에서 2 방향으로 이동한다.

g = 2 일 때, (3,1) 에서 3, 2 방향으로 이동한다.

g = 3 일 때, (2,2) 에서 3, 0, 3, 2 방향으로 이동한다.

..

 

즉,

d[0] = 1

d[1] = 2

d[2] = 3, 2

d[3] = 3, 0, 3, 2 

... 

 

이므로, 

g = n 일 때에는 d[n-1]을 뒤집고,  각 요소 d[n-1][i]에 1을 더한 후 4로 나눈 나머지가 해당 세대에 이동할 방향이 된다. 

 

x, y 좌표는 이 방향에 따라 계속 갱신해주면 된다. 

 

해당 부분을 코드로 구현하면, 

def sol(x, y, d, n):

    tmp_d = [d,]
    tmp_xy = [(x,y),]

    x += directions[d][0]
    y += directions[d][1]

    tmp_xy.append((x,y))


    for i in range(n): #세대만큼 반복

        nd = len(tmp_d)
        for i in range(nd-1, -1, -1):
            d = (tmp_d[i] + 1) % 4
            x += directions[d][0]
            y += directions[d][1]
            tmp_xy.append((x, y))
            tmp_d.append(d)
    return tmp_xy

 

위와 같이 작성할 수 있다.

먼저 0번째 커브를 이동해주고, 세대만큼 반복한다. 

이동 벡터(tmp_d)에 이동한 방향을 계속 추가하기 때문에 tmp_d의 맨 뒤에서부터 값을 가져와서 이동 방향을 구해주면 된다. 

 

내 코드

# x, y
directions = [(1, 0), (0,-1), (-1, 0), (0, 1)]

N = int(input())
curves = [[int(x) for x in input().split()] for _ in range(N)]

checks = [(1, 0), (1,-1), (0, -1)]


def sol(x, y, d, n):

    tmp_d = [d,]
    tmp_xy = [(x,y),]

    x += directions[d][0]
    y += directions[d][1]

    tmp_xy.append((x,y))


    for i in range(n): #세대만큼 반복

        nd = len(tmp_d)
        for i in range(nd-1, -1, -1):
            d = (tmp_d[i] + 1) % 4
            x += directions[d][0]
            y += directions[d][1]
            tmp_xy.append((x, y))
            tmp_d.append(d)
    return tmp_xy

def check(x, y):
    for ix, iy in checks:
        if (x+ix, y+iy) not in xy:
            return 0
    return 1


xy = []
for x, y, d, g in curves:
    xy.append(sol(x, y, d, g))

xy = [ x for y in xy for x in y ] # 2차원 리스트를 1차원으로
xy = set(xy)

count = 0
for x, y in xy:
    if check(x, y):
        count += 1

print(count)