[백준15685/골드3] 드래곤 커브 - Python

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

 

 

드래곤 커브를 어떻게 구현할지 많이 고민했다.

그래서

1. 현재까지의 드래곤 커브 좌표 리스트를 좌표이동하여 붙이는 방법

2. 현재까지의 드래곤 커브 방향을 회전하여 이어붙이는 방법

두가지로 할 수 있지 않을까 생각했다.

 

1번으로 하면 좌표 연산량이 많아지고 매번 좌표 튜플을 저장해야해서 메모리 사용량이 증가할 것 같았다.

그래서 2번으로 구현 시작했다.

 

먼저 네 좌표로 정사각형이 되는지 확인하는 함수를 만들었다.

 

mp = [[False] * 101 for _ in range(101)]

# 정사각형 체크
def check(i, j):

    if mp[i][j] and mp[i+1][j] and mp[i][j+1] and mp[i+1][j+1]:
        return 1
    return 0

 

드래곤 커브의 맵을 만들떄 주의할 점은 배열의 크기를 101 * 101로 해야한다는 점이다.

(0, 0) 부터 시작해서 100칸이 있으니 한칸이 더 추가된다.

 

 

그리고 드래곤 커브 좌표 방문표시하는 함수를 만들었다.

먼저 처음 방향과 몇세대 드래곤 커브인지 파라미터로 받은 후

g세대 드래곤 커브만큼 좌표와 화살표를 회전하고 이동하면서 방문표시 한다.

 

드래곤커브의 이동방향 추가하는 과정은

1. 이전 세대의 드래곤 커브 방향을 거꾸로 순회

2. 이전 세대의 드래곤 커브 방향을 90도 회전한 방향을 append

이렇게 된다.

이전 세대의 드래곤 커브에서 끝점을 기준으로 회전해야하기 떄문에 거꾸로 순회하면서 추가해야한다.

direction = [(1, 0), (0, -1), (-1, 0), (0, 1)] # 오른쪽, 위쪽, 왼쪽, 아래쪽
mp = [[False] * 101 for _ in range(101)]
result = 0

# 드래곤 커브
def dragon(x, y, d, g): # 시작 좌표 x, y, 방향 d, g세대 드래곤 커브
    arr = [d] # 처음 방향 저장
    mp[x][y] = True # 처음 좌표 방문처리
	
    # g세대만큼 추가하면서 이동 방향 추가
    for _ in range(g):
        for i in range(len(arr)-1, -1, -1):
            arr.append((arr[i] + 1) % 4)
	
    # 완료한 방향대로 이동하면서 방문처리
    for nd in arr:
        x += direction[nd][0]
        y += direction[nd][1]

        if 0 <= x < 101 and 0 <= y < 101:
            mp[x][y] = True

 

 

# 성공 코드

'''
0세대 드래곤 커브 : 길이가 1인 선분
1세대 드래곤 커브 : 0세대 드래곤 커브의 끝점 -> 90도 회전 -> 0세대 드래곤 커브
2세대 드래곤 커브 : 1세대 드래곤 커브의 끝점 -> 90도 회전 -> 1세대 드래곤 커브
3세대 드래곤 커브 : 2세대 드래곤 커브의 끝점 -> 90도 회전 -> 2세대 드래곤 커브
'''

N = int(input())
direction = [(1, 0), (0, -1), (-1, 0), (0, 1)] # 오른쪽, 위쪽, 왼쪽, 아래쪽
mp = [[False] * 101 for _ in range(101)]
result = 0

# 드래곤 커브
def dragon(x, y, d, g):
    arr = [d]
    mp[x][y] = True

    for _ in range(g):
        for i in range(len(arr)-1, -1, -1):
            arr.append((arr[i] + 1) % 4)

    for nd in arr:
        x += direction[nd][0]
        y += direction[nd][1]

        if 0 <= x < 101 and 0 <= y < 101:
            mp[x][y] = True

# 정사각형 체크
def check(i, j):

    if mp[i][j] and mp[i+1][j] and mp[i][j+1] and mp[i+1][j+1]:
        return 1
    return 0

for _ in range(N):
    x, y, d, g = map(int, input().split()) # 시작점, 방향, 커브 종류
    dragon(x, y, d, g)

for a in range(100):
    for b in range(100):
        result += check(a, b)

print(result)

 

 

처음에 x, y 좌표의 순서가 거꾸로 주어져서 당황했지만 어차피 배열의 크기가 정사각형이니 따로 조정해주진 않았다.