[백준 15685] 드래곤 커브

문제 보기

이 문제는 시뮬레이션 문제이다.

처음에 이 문제에서 요구하는 바가 무엇인지 이해를 하지 못했다.. 그러나 문제를 이해하고 나니 구현은 매우 쉬웠다.

드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있다.

1. 시작 점

2. 시작 방향

3. 세대 (Generation)

다음 세대로 넘어갈 때마다 변화하는 드래곤 커브는 문제의 설명을 보면 이해할 수 있다.

드래곤 커브의 진행방향은 다음과 같이 정의되어 있다.

드래곤 커브의 방향을 살펴보면 다음과 같은 규칙이 있다.

0세대: 0

1세대: 01 -------------- 0 1

2세대: 0121 ----------- 01 21

3세대: 01212321 ------ 0121 2321

위의 규칙을 보면, 다음 세대의 드래곤 커브는 현재 세대의 드래곤 커브에서 거꾸로 순회하면서 시계방향으로 90도 회전시킨 것을 현재 커브에 더해준 것과 같다.

문제를 푼 로직은 다음과 같다.

1. 주어진 세대까지 드래곤 커브의 방향들을 구한다. (12~15번째 줄)

2. 주어진 좌표로부터 현재 세대까지의 드래곤 커브의 좌표들을 구한다. (17~24번째 줄)

3. 정사각형의 네 꼭지점이 드래곤 커브의 일부가 되는 갯수를 구한다. (26~31번째 줄)

import sys
n = int(sys.stdin.readline())
dragon_curves = [list(map(int, sys.stdin.readline().split())) for i in range(n)]
 
visited = set()
directions = ((0, 1), (-1, 0), (0, -1), (1, 0))
for c, r, d, g in dragon_curves:
    moves = list()
    moves.append(d)
    # for each generation
    for i in range(g):
        # append reversed element of movements
        for move in moves[::-1]:
            next_move = (move + 1) % 4
            moves.append(next_move)
    
    # check coordination of all movements of dragon curve
    cur_r, cur_c = r, c
    visited.add((cur_r, cur_c))
    for move in moves:
        next_r = cur_r + directions[move][0]
        next_c = cur_c + directions[move][1]
        visited.add((next_r, next_c))
        cur_r, cur_c = next_r, next_c
 
# check square
answer = 0
for i in range(101):
    for j in range(101):
        if (i, j) in visited and (i, j + 1) in visited and (i + 1, j) in visited and (i + 1, j + 1) in visited:
            answer += 1
print(answer)