[Algorithm | Python] BOJ-15685 : 드래곤 커브

BOJ-15685 : 드래곤 커브

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

풀이 방법

이 문제는 드래곤 커브를 생성한 뒤, 1x1 정사각형이 몇개 만들어지는지 구하는 문제다.

드래곤 커브는 세대가 증가할 때마다 이전 세대의 선분을 시계 방향으로 90도 회전한 형태로 확장되는 구조를 가지고 있다.

문제 해결 과정은 다음과 같다.

1. 각 드래곤 커브의 방향 정보를 생성한다.

2. 방향 정보를 이용해 실제 좌표에 커브를 그린다.

3. 모든 커브를 그린 뒤, 정사각형의 개수를 계산한다.

Idea

이 문제를 처음 보면 드래곤 커브의 모양을 직접 좌표로 계산하려고 하다가 막히기 쉽다.

세대가 증가할수록 곡선의 모양이 계속 변하기 때문에 다음 좌표를 어떻게 계산해야 하는지 감이 잘 잡히지 않는다.

처음에는 “다음 세대의 커브를 어떻게 좌표로 만들어야 할까?”라는 생각으로 접근했지만, 문제를 조금 더 관찰해보면 중요한 사실 하나를 발견할 수 있다.

드래곤 커브는 결국 격자 위에서 한 칸씩 이동하며 선을 그리는 과정이다.

즉 실제로 필요한 정보는 좌표 자체가 아니라 어느 방향으로 이동하느냐이다.

이 점에 착안하면 커브 전체를 좌표로 계산하려고 할 필요 없이, 이동 방향의 순서만 생성하면 된다는 것을 알 수 있다.

세대 변화 관찰

드래곤 커브는 세대가 증가할 때 다음과 같은 특징을 가진다.

현재 커브의 끝점에서 이전 커브를 90도 회전한 형태로 붙인다.

이 특징을 실제 커브 모양을 그려보며 관찰하면 한 가지 규칙이 보인다.

새로운 세대를 만들 때 추가되는 방향들은 단순히 새로 계산되는 것이 아니라, 기존 방향들의 변형된 형태라는 것이다.

특히 끝점을 기준으로 회전하여 붙는 구조이기 때문에, 추가되는 방향들은 기존 방향을 거꾸로 따라가며 회전한 형태로 나타난다.

이 관찰을 통해 다음과 같은 규칙을 발견할 수 있다.

방향 리스트 생성 규칙

드래곤 커브의 방향 정보는 다음과 같은 방식으로 확장된다.

현재 방향 리스트가 있다면,

다음 세대의 방향 리스트는 기존 방향 리스트 뒤에 기존 리스트를 역순으로 보면서 90도 회전한 방향들을 추가하는 방식으로 생성된다.

이렇게 방향 정보를 확장해 나가면 각 세대의 이동 경로가 자연스럽게 만들어진다.

이 방법의 장점은 드래곤 커브를 좌표로 직접 계산하지 않아도 된다는 점이다.

단순히 방향의 순서를 만들어 놓은 뒤, 시작 좌표에서 해당 방향으로 한 칸씩 이동하기만 하면 실제 커브가 완성된다.

시간 복잡도

드래곤 커브 생성

O(N * 2^g) N <= 20 g <= 10 최대 20 * 1024 ≈ 20,480

정사각형 검사

100 * 100 = 10,000

총 연산량

약 30,000

따라서 완전 시뮬레이션으로 충분히 해결 가능하다.

Code

N = int(input())

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

DIR = [
    [0, 1],
    [-1, 0],
    [0, -1],
    [1, 0],
]


def draw_arr(x, y, d, g):
    global arr

    # 방향 리스트 구하기
    cur_g = 0
    directions = [d]
    while cur_g < g:
        cur_g += 1
        next_directions = directions[::-1]
        for i in range(len(next_directions)):
            next_directions[i] = (next_directions[i] + 1) % 4
        directions = directions + next_directions

    # 좌표 표기하기
    nx, ny = x, y
    arr[ny][nx] = True
    for i in directions:
        ny, nx = ny + DIR[i][0], nx + DIR[i][1]
        arr[ny][nx] = True


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


def check(r, c):
    return 0 <= r < 100 and 0 <= c < 100


result = 0
for r in range(101):
    for c in range(101):
        # 현재 점 체크
        if not check(r, c): continue
        if not arr[r][c]: continue

        if not arr[r][c + 1]: continue  # 우
        if not arr[r + 1][c]: continue  # 하
        if not arr[r + 1][c + 1]: continue  # 우측 아래 대각선

        # 개수 카운트
        result += 1

print(result)

정리

처음에는 드래곤 커브의 좌표를 직접 계산하려고 했지만, 문제를 관찰하면서 좌표보다 중요한 것은 이동 방향의 순서라는 사실을 깨닫게 된다.

따라서 이 문제의 핵심은 드래곤 커브의 모양을 계산하는 것이 아니라, 세대에 따라 확장되는 방향 리스트를 만드는 것이라고 볼 수 있다.

이렇게 방향 리스트를 생성한 뒤 그 방향대로 이동하며 격자에 표시하면, 마지막에는 네 꼭짓점이 모두 채워진 1×1 정사각형의 개수를 세는 방식으로 문제를 해결할 수 있다.