15685번. 드래곤 커브

http://boj.kr/15685 

 

 

규칙을 찾아내면 되는 문제이다.

(x, y) 증가량으로 규칙을 찾아내려고 하면 눈에 잘 보이지 않는다.

문제에서 제시한 

 

• 0: x좌표가 증가하는 방향 (→)
• 1: y좌표가 감소하는 방향 (↑)
• 2: x좌표가 감소하는 방향 (←)
• 3: y좌표가 증가하는 방향 (↓)

를 사용한다.

0세대에서부터 K세대까지 직접 그려보는데,

새로 생겨난 변의 번호를 직접 써보면 규칙이 보인다.

K세대 드래곤 커브의 각 선분 정보를 담은 리스트를 directions 라고 하면,

K+1세대 드래곤 커브의 것은 directions을 역순으로 하고 (x+1)%4 한 것이다.

import sys


# 네 꼭짓점이 모두 드래곤 커브인 정사각형 갯수 구하기
def calc():
    ret = 0
    for i in range(SZ):
        for j in range(SZ):
            if j < SZ - 1 and i < SZ - 1:
                if board[i][j] and board[i + 1][j] and board[i][j + 1] and board[i + 1][j + 1]:
                    ret += 1
    return ret


def draw(x, y, d, generation):
    # draw 0st dragon
    directions = [d]
    board[x][y] = 1
    x += dx[d]
    y += dy[d]
    board[x][y] = 1

	# draw Kst dragons
    for g in range(1, generation + 1):
        tmp = []  # 이번 세대에 새로 생긴 선분들의 방향
        for d in reversed(directions):  # 역순
            d = (d + 1) % 4
            tmp.extend([d])
            x += dx[d]
            y += dy[d]
            board[x][y] = 1
        directions.extend(tmp)  # directions 업데이트


SZ = 101  # 전체 좌표의 크기. 0 <= x, y <= 100 이므로 크기는 101이 되어야 함
input = sys.stdin.readline
N = int(input())
all_curves = [list(map(int, input().split())) for _ in range(N)]
board = [[0] * SZ for _ in range(SZ)]
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

for x, y, d, g in all_curves:  
    draw(y, x, d, g)  
    # 문제에서의 (x, y) = (col, row)이므로 여기서만 거꾸로 전달하고
    # 나머지 보드 위에서의 움직임은 원래 하던 row, col으로 하면 된다.

print(calc())