BOJ - 드래곤 커브 15685번 (python)

❓ 문제 - 백준 드래곤 커브 15685번 - python 풀이법

출처 

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

15685번: 드래곤 커브

 

 

📝 문제해결법

1. 이 문제는 Stack+구현으로 풀었다.

• visited 리스트를 통해 드래곤 커브로 그려지면 방문처리를 해준다. 
• 드래곤 커브 후 정사각형의 갯수를 구할 때는 visited 리스트를 이용하여 격자판의 범위 (0~100 행, 0 ~100열)에서 현재 위치 행 ~ 현재위치 행 +1, 현재위치 열 ~ 현재위치 열 +1의 정사각형 모양으로 모두 방문처리(드래곤 커브 그려짐) 되었다면 정사각형의 갯수 count를 1 증가시킨다.
• dragon() 함수는 드래곤 커브를 그리는 함수이다.
• 드래곤 커브를 구현하는 방법은 드래곤 커브를 그리는 위치(x, y)에서 어떤 방향(d)으로 이동 한 후, 이동하는 방향들을 stack에 append 한다. 다음 세대의 드래곤 커브를 그릴 때, stack에서 top 값을 pop한 후 해당 방향의 (d + 1) % 4 해주면 90도 기울여진 방향이 나와서 해당 방향으로 이동한 후 방문처리 해준다.
• 예를 들어, x=3, y=3, d=0 g=1의 드래곤 커브를 그리면 현재 위치(x, y)를 방문처리 해주고 0세대에 (3,3)에서 방향(1=북)으로 이동한 nx, ny에서도 방문처리를 해준다. 또한 stack에 이동방향 d를 append 해준다. 또한 1세대부터 드래곤 커브를 그리면 stack에 있는 값들을 copy한 stack_copy의 top값을 pop하면 방향 0(=동)이며  (d + 1) % 4의 값을 변경을 통해 90도 회전하면 방향은 1(=북)가 된다. 따라서 1세대의 진행방향은 북이며 이때 이동하여 해당 위치를 방문처리한다. 또한 진행방향을 stack에 append 한 후, 드래곤 커브 그리기를 종료한다.
• 드래곤 커브는 격자 밖으로 벗어나지 않는다. 라고 문제에 적혀 있으므로 해당 방향으로 이동한 값 nx, ny의 범위를 고려할 필요가 없다.
• x, y할 때 행,열이 아니라 함수에 사용되는 x, y이므로 열, 행으로 구현해야한다.

 

 

💻 소스코드

import copy
n = int(input())
visited = [[False] * (101) for _ in range(101)]

# 동 - 북 - 서 - 남
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

def dragon(x, y, dir, g):
    stack = []
    visited[x][y] = True
    nx, ny = x + dx[dir], y + dy[dir]
    visited[nx][ny] = True
    stack.append(dir)
    for i in range(1, g+1):
        stack_copy = copy.deepcopy(stack)
        while stack_copy:
            d = stack_copy.pop()
            d = (d + 1) % 4
            nx += dx[d]
            ny += dy[d]
            visited[nx][ny] = True
            stack.append(d)

for _ in range(n):
    x, y, d, g = map(int, input().split())
    dragon(y, x, d, g)


count = 0


for i in range(0, 100):
    for j in range(0, 100):
        if visited[i][j] and visited[i+1][j] and visited[i][j+1] and visited[i+1][j+1]:
            count += 1

print(count)