풀이


nxn 배열에 그려진 커브를 활용해 만들 수 있는 1x1 정사각형을 갯수를 출력하는 문제이다.

1x1 정사각형의 갯수는 board[i][j] and board[i][j+1] and board[i+1][j] and board[i+1][j+1] 를 통해 쉽게 구해낼 수 있기 때문에 드래곤커브를 보드에 그리는 것이 중요하다.

해당 문제는 x 좌표가 우측으로 증가하고 y 좌표가 아래로 증가하기 때문에 입력을 받을 때 x 를 row 로 y 를 column 으로 인식해야한다.

또한 드래곤 커브의 세대에 따라 커브가 변경되는데 이때의 패턴을 잘 알아야한다.

방향 0, 1, 2, 3 은 각각 동, 북, 서, 남을 의미하기 때문에 숫자들을 인덱스로 활용하여 dx dy 를 선언해준다.

예를 들어 0세대에 우측으로 커브가 진행될 때:

0세대: [0]

1세대: [1]

2세대: [2, 1]

3세대: [2, 3, 2, 1]

방향으로 커브가 진행하게된다.

이때 알 수 있는 패턴은 전 세대들의 방향에서 1을 더한 후 거꾸로 뒤집어 준다는 것이다.

0세대: [0]

1세대: [1] = [0+1]

2세대: [2, 1] = [1+1, 0+1]

3세대: [2, 3, 2, 1] = [1+1, 2+1, 1+1, 0+1]

따라서 위 패턴대로 방향성을 구현해준 뒤 해당 방향을 인덱스로 활용하여 좌표상의 숫자를 업데이트해주면된다.

아래 코드를 봤을 때, y, x, d, g 가 4, 2, 1, 3 으로 주어졌다고 해보자.

board[2][4] = 1 이 된 후

temp = [1] 그리고 q = [1] 이 된다.

해당 드래곤 커브는 3세대까지 진행되기 때문에 0, 1, 2, 3세대 순으로 커브를 진행시킨다.

현재 q = [1] 이기 때문에 [2, 4] 였던 [x, y] 는 [1, 4] 가 된다.

이후 q 를 새로 선언해주는데, 앞서 언급했던 패턴을 그래도 구현했다.

temp 에 저장되어 있던 전 세대 방향인 [1] 을 [2] 로 변환하고 이후 세대에 쓰일 temp 에 q 를 더해준다.

현재 temp = [1, 2] 그리고 q = [2] 인 상황이고 1세대 드래곤 커브를 그릴 차례이다.

[1, 4] 였던 [x, y] 는 [1, 3] 이 되고, q 는 temp 요소들에 1을 더한 후 뒤집어 준 [3, 2] 가 된다.

이제 temp = [1, 2, 3, 2] 그리고 q = [3, 2] 이며, 2세대 드래곤 커브를 그릴 차례이다.

[1, 3] 이였던 [x, y] 는 q 를 순회하며 [4, 2], [3, 2] 를 거치며 q 는 다시 [3, 0, 3, 2] 가 된다.

이제 마지막 3세대 드래곤 커브를 그릴 차례이며 temp = [1, 2, 3, 2, 3, 0, 3, 2] 이고 q = [3, 0, 3, 2] 이다.

[3, 2] 였던 [x, y] 는 q 를 순회하며 [4, 2], [4, 3], [5, 3], [4, 3] 을 거치고 반복문은 종료된다.

[2, 4] 에서 시작한 드래곤 커브는,

0세대: [1, 4]

1세대: [1, 3]

2세대: [4, 2], [3, 2]

3세대: [4, 2], [4, 3], [5, 3], [4, 3]

를 거쳐 총 9개의 점을 지나 8개의 선을 그리게된다.

처음엔 trigonometry 를 사용해서 다음 좌표를 구해야하나 싶었지만 패턴이 있어 해당 패턴을 활용하여 문제를 풀었다.

상당히 어려운 구현문제였기에 복습할 필요가 있을 것 같다.

소스코드


# 드래곤 커브
import sys
input = sys.stdin.readline
 
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]
board = [[0] * 101 for _ in range(101)]
 
for _ in range(int(input())):
    y, x, d, g = map(int, input().split())
    board[x][y] = 1
    temp = [d]
    q = [d]
    for _ in range(g+1):
        for i in q:
            x += dx[i]
            y += dy[i]
            board[x][y] = 1
        q = [(t+1)%4 for t in temp]
        q.reverse()
        temp += q
 
ans = 0
 
for i in range(100):
    for j in range(100):
        if board[i][j] and board[i][j+1] and board[i+1][j] and board[i+1][j+1]:
            ans += 1
 
print(ans)

References