백준 15685번: 드래곤 커브 (Python)

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

15685번: 드래곤 커브

접근

세대가 증가할 때 드래곤 커브의 규칙성만 파악하면 쉽게 구현할 수 있는 문제였다. 그 규칙성은 아래와 같다.

0:동쪽, 1:북쪽, 2:서쪽, 3:남쪽

어느 방향으로 출발하던 규칙성은 같으므로 편의를 위해 첫 출발 방향이 0이라고 생각하면

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

와 같은 순서로 진행하게 된다.

여기서 규칙성을 파악해보면, 세대가 올라갈 때에 그 전 세대 진행 순서를 역순으로 +1 하여 추가로 진행한다고 볼 수 있다.
2세대가 0 1 2 1로 진행했다면 이를 역순으로 정렬하면 1 2 1 0, 여기에 모두 +1 해주면 2 3 2 1 이 된다. 2세대 뒤에 이 2 3 2 1을 추가해주면 3세대가 된다.
마찬가지로 계산해보면

4세대: 0 1 2 1 2 3 2 1 / 2 3 4(0) 3 2 3 2 1

보이는대로 4는 0으로 바꾸어주면(더한 값을 4로 나눈 나머지 계산) 4세대가 정확히 구해지게 된다. 다른 방향으로 출발해도 같은 규칙이 적용된다.

이와 같은 방식으로 드래곤 커브를 그려주는 dragon_curve 함수를 작성해주고, 네 꼭지점이 드래곤 커브의 일부인 칸의 수를 카운트해주면 답을 구할 수 있다.

코드

rc = [0, -1, 0, 1]
cc = [1, 0, -1, 0]
matrix = [[0] * 101 for _ in range(101)]


def dragon_curve(r, c, d, g):
    curve = [d]
    ng = 0
    matrix[r][c] = 1
    r, c = r + rc[d], c + cc[d]
    matrix[r][c] = 1
    while ng < g:
        for i in range(len(curve) - 1, -1, -1):
            r, c = r + rc[(curve[i] + 1) % 4], c + cc[(curve[i] + 1) % 4]
            curve.append((curve[i] + 1) % 4)
            matrix[r][c] = 1
        ng += 1


N = int(input())
for _ in range(N):
    c, r, d, g = map(int, input().split())
    dragon_curve(r, c, d, g)
cnt = 0
for i in range(len(matrix) - 1):
    for j in range(len(matrix) - 1):
        if (
            matrix[i][j] == 1
            and matrix[i + 1][j] == 1
            and matrix[i][j + 1] == 1
            and matrix[i + 1][j + 1] == 1
        ):
            cnt += 1
print(cnt)

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!