풀이
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)