문제 설명
드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다.
- 시작 점
- 시작 방향
- 세대
0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다. 아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다.
1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝 점에 붙인 것이다. 끝 점이란 시작 점에서 선분을 타고 이동했을 때, 가장 먼 거리에 있는 점을 의미한다.
2세대 드래곤 커브도 1세대를 만든 방법을 이용해서 만들 수 있다. (파란색 선분은 새로 추가된 선분을 나타낸다)
3세대 드래곤 커브도 2세대 드래곤 커브를 이용해 만들 수 있다. 아래 그림은 3세대 드래곤 커브이다.
즉, K(K > 1)세대 드래곤 커브는 K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시킨 다음, 그것을 끝 점에 붙인 것이다.
크기가 100×100인 격자 위에 드래곤 커브가 N개 있다. 이때, 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수를 구하는 프로그램을 작성하시오. 격자의 좌표는 (x, y)로 나타내며, 0 ≤ x ≤ 100, 0 ≤ y ≤ 100만 유효한 좌표이다.
입력
첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10)
입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 드래곤 커브는 서로 겹칠 수 있다.
방향은 0, 1, 2, 3 중 하나이고, 다음을 의미한다.
- 0: x좌표가 증가하는 방향 (→)
- 1: y좌표가 감소하는 방향 (↑)
- 2: x좌표가 감소하는 방향 (←)
- 3: y좌표가 증가하는 방향 (↓)
출력
첫째 줄에 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력한다.
전체 코드
#direction (right,up,left,down)
from collections import deque
import copy
dx=(0,-1,0,1)
dy=(1,0,-1,0)
#get directions of dragon curve with stack and queue
def get_direction(curve):
start_dir=curve[2]
generation=curve[3]
#stack for saving directions , append, pop
dir_stack=deque()
dir_stack.append(start_dir)
for i in range(generation):
#copy original stack
temp_stack=copy.deepcopy(dir_stack)
#queue for saving temp directions, append, popleft
temp_queue=deque()
while temp_stack:#while temp_stack is not empty
popped=temp_stack.pop()
#rotate 90 degree
rotated=(popped+1)%4
temp_queue.append(rotated)
while temp_queue:#while temp_queue is not empty
popped=temp_queue.popleft()
dir_stack.append(popped)
return dir_stack
#with direction stack, collect (x,y) of dragon curve
def get_dimensions(curve,dir_stack):
x=curve[0]
y=curve[1]
dimension=[]
dimension.append((x,y))
for i in range(len(dir_stack)):
direction=dir_stack[i]
x=x+dx[direction]
y=y+dy[direction]
dimension.append((x,y))
return dimension
n=int(input())
curves=[]
for i in range(n):
data=list(map(int,input().split()))
#y->x, x->y, start direction, generation
curves.append((data[1],data[0],data[2],data[3]))
arr=[[0]*101 for _ in range(101)]
for curve in curves:
dir_stack=get_direction(curve)
dimension=get_dimensions(curve,dir_stack)
for d in dimension:
x=d[0]
y=d[1]
arr[x][y]=1
answer=0
for i in range(len(arr)):
for j in range(len(arr[i])):
if i+1>=len(arr) or j+1>=len(arr[i]):
continue
if arr[i][j]==1 and arr[i][j+1]==1 and arr[i+1][j]==1 and arr[i+1][j+1]==1:
answer+=1
print(answer)해설
1. 규칙성을 판단하여 드래곤 커브를 구현한다.
아래 그림은 3세대 그림이다. (처음에는 방향에 대한 규칙을 못 찾아서 헤맸었다.)
0세대 기준으로 →
1세대 기준으로 ↑
2세대 기준으로 ←,↑
3세대 기준으로 ←,↓, ←,↑이다.
규칙성을 파악해보면, k 세대는 k-1 세대의 방향들을 역순으로 모아서 각각의 방향들에 대해 90도 회전 시킨 방향들을 추가한 것이라 볼 수 있다.
예를 들면, 1세대는 0세대 [→] 방향에 대해 90도 회전 시켜 ↑방향을 가진다.
1세대 [→,↑] 방향에 대해 역순으로 모으면 [↑,→]이고 이를 각각 90도 회전시키면 [←,↑]다. 이를 기존 1세대에 추가하면 2세대[→,↑←,↑]다.
2세대 [→,↑,←,↑]를 역순으로 모으면 [↑,←,↑→]이고 이를 각각 90도 회전시키면 [←,↓,←,↑]다. 이를 기존 2세대에 추가하면 3세대 [→,↑←,↑,←,↓,←,↑]다.
위 로직은 스택과 큐를 활용하면 간결하게 구현할 수 있다.
각 세대의 방향은 누적되며, 다음 세대의 방향의 참고가 된다. 즉, 쌓이는 형태이므로 스택에 방향들을 담아 놓는다.
그리고 k-1세대의 방향들을 역순으로 모으고 90도 회전하는 것은 k-1세대의 사본 스택에서 pop()한 후, 90도를 회전시킨 것을 큐에 담으면 된다.
(이전 세대들의 방향도 스택에 계속 남겨져 있어야 하기 때문에 원본 대신 복사본을 만들어 pop()해야 한다.)
마지막으로 큐에 담긴 것을 다시 복사본 스택에 넣어주면 된다.
이를 코드로 표현하면 다음과 같다. 리턴 값은 방향이 쌓여 있는 스택이다.
#direction (right,up,left,down)
from collections import deque
import copy
dx=(0,-1,0,1)
dy=(1,0,-1,0)
#get directions of dragon curve with stack and queue
def get_direction(curve):
start_dir=curve[2]
generation=curve[3]
#stack for saving directions , append, pop
dir_stack=deque()
dir_stack.append(start_dir)
for i in range(generation):
#copy original stack
temp_stack=copy.deepcopy(dir_stack)
#queue for saving temp directions, append, popleft
temp_queue=deque()
while temp_stack:#while temp_stack is not empty
popped=temp_stack.pop()
#rotate 90 degree
rotated=(popped+1)%4
temp_queue.append(rotated)
while temp_queue:#while temp_queue is not empty
popped=temp_queue.popleft()
dir_stack.append(popped)
return dir_stack
n=int(input())
curves=[]
for i in range(n):
data=list(map(int,input().split()))
#y->x, x->y, start direction, generation
curves.append((data[1],data[0],data[2],data[3]))
arr=[[0]*101 for _ in range(101)]
for curve in curves:
dir_stack=get_direction(curve)2.드래곤 커브를 다 만든 후 , 드래곤 커브가 거쳐간 좌표들을 수집한다.
1.에서 방향 스택을 만들었으면, 방향에 따라 좌표들을 수집해야 한다.
1.을 구현했으면 2.는 어려울 것이 없다.
좌표들을 수집한 dimension 리스트를 보고 해당되는 arr[x][y]에 1표시를 해준다.
#with direction stack, collect (x,y) of dragon curve
def get_dimensions(curve,dir_stack):
x=curve[0]
y=curve[1]
dimension=[]
dimension.append((x,y))
for i in range(len(dir_stack)):
direction=dir_stack[i]
x=x+dx[direction]
y=y+dy[direction]
dimension.append((x,y))
return dimension
n=int(input())
curves=[]
for i in range(n):
data=list(map(int,input().split()))
#y->x, x->y, start direction, generation
curves.append((data[1],data[0],data[2],data[3]))
arr=[[0]*101 for _ in range(101)]
for curve in curves:
dir_stack=get_direction(curve)
dimension=get_dimensions(curve,dir_stack)
for d in dimension:
x=d[0]
y=d[1]
arr[x][y]=13.100 x 100 행렬을 2 x 2의 크기로 전수조사한다.
범위가 벗어나는 값을 제외하고 2 x 2의 크기로 전수조사해서 해당 영역이 모두 1로 표시되있으면 정답 개수 +1을 해준다.
answer=0
for i in range(len(arr)):
for j in range(len(arr[i])):
if i+1>=len(arr) or j+1>=len(arr[i]):
continue
if arr[i][j]==1 and arr[i][j+1]==1 and arr[i+1][j]==1 and arr[i+1][j+1]==1:
answer+=1
print(answer)