[백준] 15685 드래곤 커브 python 풀이

문제

• 난이도: 골드3
• 알고리즘 분류: 구현, 시뮬레이션
• 요약: 주어진 정보를 통해 n개의 드래곤 커브를 구현했을 때, 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력하기

풀이

커브 구하기

각 세대마다 생성되는 커브의 개수와 방향에 관한 규칙을 살펴보았다.
동(0) 북(1) 서(2) 남(3)

세대	선분의 개수	방향
0	1 (2^0)	0
1	2 (2^1)	0 1
2	4 (2^2)	0 1 2 1
3	8 (2^3)	0 1 2 1 2 3 2 1

세대가 증가할수록 선분의 개수는 2배씩 증가하고,
방향은 이전 세대의 리스트의 마지막 원소부터 90도 회전한 방향으로 추가되는 것을 볼 수 있다.

방문 여부 표시

드래곤 커브 좌표를 표시하기 위해 visited 2차원 배열을 생성하고, 방문한 좌표에 대한 값을 업데이트한다. curve 리스트에 담아둔 방향을 주어진 y, x 방향부터 시작하여 이동하고 방문 처리를 한다.

코드

import sys

input = sys.stdin.readline

n = int(input())

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

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

for _ in range(n):
    x, y, d, g = map(int, input().split())
    visited[y][x] = True

    curve = [d] # 시작 방향
    for _ in range(g): # 세대
        for i in range(len(curve) -1, -1, -1):
            next_d = (curve[i] + 1) % 4
            curve.append(next_d)

    for d in curve:
        x += dx[d]
        y += dy[d]

        if 0 <= y <= 100 and 0 <= x <= 100:
            visited[y][x] = True

count = 0
for r in range(100):
    for c in range(100):
        if visited[r][c] == True and visited[r][c+1] == True and \
            visited[r+1][c] == True and visited[r+1][c+1] == True:
            count += 1
print(count)