[BOJ15685 - Python] 드래곤 커브

문제

---

15685번: 드래곤 커브

 

K(K>1)세대 드래곤 커브

= K-1세대 드래곤 커브를 끝 점 기준 90도 시계 방향으로 회전 → 그 끝 점에 붙인 것

 

 

풀이

---

첫번째 풀이

드래곤 커브로 그려진 선분을 역순으로 추적하여 '시계 방향 90도 회전 → 끝 점에 붙이기'를 반복하는 것을 통해 직접 좌표들을 계산했다.

선분의 방향마다 그 다음으로 찍혀야 하는 점의 위치를 고려해주어야 하기 때문에

해당 방향 벡터가 시계 방향으로 90도 회전하면 어느 방향 벡터로 바뀌는지에 대한 딕셔너리를 만들어주었다.

{ 방향 벡터 : 시계 방향 90도 회전 후의 방향 벡터 }

rotate_90 = {(-1, 0): (0, 1), (1, 0): (0, -1), (0, 1): (1, 0), (0, -1): (-1, 0)}  # 시계 방향 90도 회전 시 벡터

선분의 거리는 항상 1이기 때문에 "끝 점 - 시계 방향 90도 회전 후의 방향 벡터"를 통해 다음으로 찍히는 점들을 찾아낼 수 있다.

 

전체 코드는 다음과 같다.

import sys

N = int(sys.stdin.readline().strip())

dragon_input = []  # 시작점 x, 시작점 y, 시작 방향, 세대
for _ in range(N):
    dragon_input.append(list(map(int, sys.stdin.readline().split())))

grid = []  # 100 x 100
for _ in range(101):
    grid.append(list([False for _ in range(101)]))

direction = [(0, 1), (-1, 0), (0, -1), (1, 0)]  # 시작 방향
rotate_90 = {(-1, 0): (0, 1), (1, 0): (0, -1), (0, 1): (1, 0), (0, -1): (-1, 0)}  # 시계 방향 90도 회전 시 벡터

for start_x, start_y, d, g in dragon_input:
    dragon = [[start_y, start_x], [start_y + direction[d][0], start_x + direction[d][1]]]  # 드래곤 커브 좌표 (0세대)

    for _ in range(g):
        i = len(dragon) - 1

        # 드래곤 커브 좌표 구하기
        while i >= 1:
            y = dragon[i][0] - dragon[i - 1][0]
            x = dragon[i][1] - dragon[i - 1][1]

            vector = rotate_90.get((y, x))
            new_point = [dragon[-1][0] - vector[0], dragon[-1][1] - vector[1]]
            dragon.append(new_point)

            i -= 1

    # 위치 표시
    for d_y, d_x in dragon:
        grid[d_y][d_x] = True

# 정사각형 개수 구하기
result = 0
for y in range(100):
    for x in range(100):
        if grid[y][x] and grid[y + 1][x] and grid[y][x + 1] and grid[y + 1][x + 1]:
            result += 1
print(result)

어찌저찌 성공하긴 했지만 굉장히 마음에 들지 않는다.

 

두번째 풀이

사실 알고리즘 관련 블로깅은 처음 하다보니까 어떻게 써야할지 너무 막막해서 다른 분들의 블로그를 열심히 찾아봤는데,

이 과정에서 내 풀이보다 훨씬 나은 아이디어들을 보았다.

바로 다시 코딩 고고.

 

문제 설명에서 처럼

0 : x좌표가 증가하는 방향 (→)

1 : y좌표가 감소하는 방향 (↑)

2 : x좌표가 감소하는 방향 (←)

3 : y좌표가 증가하는 방향 (↓)

이라고 했을 때

 

드래곤 커브 세대별로 선분마다의 방향을 쭉 작성해보면

0세대 : 0

1세대 : 0 1

2세대 : 0 1 2 1

3세대 : 0 1 2 1 2 3 2 1

...

 

조금 더 규칙을 보기 쉽게 작성해보면

0세대 : 0

1세대 : 0 / 1

2세대 : 0 1 / 2 1

3세대 : 0 1 2 1 / 2 3 2 1

...

즉, '이전 세대의 방향 + 1'을 역순으로 이어 붙여주면 되는 것이었다.

 

이렇게 찾은 규칙으로 수정한 전체 코드는 다음과 같다.

import sys

N = int(sys.stdin.readline().strip())

dragon_input = []  # 시작점 x, 시작점 y, 시작 방향, 세대
for _ in range(N):
    dragon_input.append(list(map(int, sys.stdin.readline().split())))

grid = []  # 100 x 100
for _ in range(101):
    grid.append(list([False for _ in range(101)]))

# 방향
d_y = [0, -1, 0, 1]
d_x = [1, 0, -1, 0]

for start_x, start_y, d, g in dragon_input:
    direction = [d]

    for _ in range(g):
        for i in range(len(direction) - 1, -1, -1):  # range(start, stop, step)
            direction.append((direction[i] + 1) % 4)

    # 위치 표시
    grid[start_y][start_x] = True
    for i in direction:
        start_y += d_y[i]
        start_x += d_x[i]
        grid[start_y][start_x] = True

# 정사각형 개수 구하기
result = 0
for y in range(100):
    for x in range(100):
        if grid[y][x] and grid[y + 1][x] and grid[y][x + 1] and grid[y + 1][x + 1]:
            result += 1
print(result)

한 리스트 내에서 좌표들을 쭉 저장하는 것보단

d_y, d_x으로 y값, x값을 따로 저장해주어 호출하는 것이 더 직관적이고 편한 것 같아 해당 방향으로 코드를 고치게 되었다.

 

만-족

 

 

앞으로 주의해야 할 사항

---

1. 문제를 잘 읽자 !!!!!!

문제에서는 크기가 1×1인 정사각형의 '네 꼭짓점'이 모두 드래곤 커브의 일부인 것의 개수를 물어봤는데, 나는 드래곤 커브의 '네 선분'으로 둘러 쌓여있어야 한다는 것으로 잘못 이해했었다. 다 구현하고 나서야 읭...?하고 깨달아버림

예에에에전부터 많이 실수하는 것인데 문제를 처음부터 잘 읽도록 하자.

 

2. grid 범위

계속 런타임 에러 (IndexError)가 나서 봤더니, 격자를 선언한 범위 때문에 나는 에러였다.

문제에서는 크기가 100×100인 격자이며 0 ≤ x ≤ 100, 0 ≤ y ≤ 100라고 했기 때문에 아래처럼 선언해주어야 한다.

(101이 아닌 100으로 작성해서 틀린 것이었다.)

grid = []  # 100 x 100
for _ in range(101):
    grid.append(list([False for _ in range(101)]))