문제 링크

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

문제 설명

• N개의 드래곤 커브가 주어짐
  • 시작점, 시작 방향, 세대
• 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수 출력

풀이

• 각 드래곤 커브에 대해서
  • 각 세대별로 (1세대, 2세대, ..., K세대)
    • 앞으로 그려야 할 방향 구함
      • 현재까지 방향 뒤집음
      • 90도씩 돌림
    • 끝점부터 방향대로 그린 후 끝점 갱신
    • 방향 갱신

후기

어려워 보였는데 생각보다 금방 풀렸다

코드

def draw(y, x, d, g, num):
    board[y][x] = num
    y, x = y + dy[d], x + dx[d]
    board[y][x] = num
    directions = [d]
    for i in range(1, g+1):
        next_directions = get_next(directions)
        y, x = draw_next(y, x, next_directions, num)
        directions += next_directions


def get_next(directions):
    next_directions = list(reversed(directions))
    for i in range(len(next_directions)):
        next_directions[i] = (next_directions[i] + 1) % 4
    return next_directions


def draw_next(y, x, directions, num):
    for d in directions:
        y, x = y + dy[d], x + dx[d]
        board[y][x] = num
    return y, x


# init
import sys
read = sys.stdin.readline
n = int(read())
info = [list(map(int, read().split())) for _ in range(n)]
dy, dx = [0, -1, 0, 1], [1, 0, -1, 0]
board = [[0] * 101 for _ in range(101)]
count = 0

# start
for i in range(len(info)):
    x, y, d, g = info[i]
    draw(y, x, d, g, i+1)
for i in range(100):
    for j in range(100):
        if board[i][j] and board[i+1][j] and board[i][j+1] and board[i+1][j+1]:
            count += 1
print(count)