[python] BOJ 백준 15685: 드래곤커브

1. 문제  

드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다.

1. 시작 점
2. 시작 방향
3. 세대

0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다. 아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다.

1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝 점에 붙인 것이다. 끝 점이란 시작 점에서 선분을 타고 이동했을 때, 가장 먼 거리에 있는 점을 의미한다.

즉, K(K > 1)세대 드래곤 커브는 K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시킨 다음, 그것을 끝 점에 붙인 것이다.

크기가 100×100인 격자 위에 드래곤 커브가 N개 있다. 이때, 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수를 구하는 프로그램을 작성하시오. 격자의 좌표는 (x, y)로 나타내며, 0 ≤ x ≤ 100, 0 ≤ y ≤ 100만 유효한 좌표이다.

2. 입력   

첫째 줄에 드래곤 커브의 개수 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좌표가 증가하는 방향 (↓)

3. 출력   

첫째 줄에 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력한다.

4. 해결방법   

이 문제는 구현, 시뮬레이션 문제이다. 드래곤커브 방향의 규칙성을 찾아야 풀수 있는 문제이다. 세대가 반복할수록 추가되는 방향에는 규칙이있는데, 이전세대의 방향을 뒤집은 값에 +1 한값이 다음세대의 방향이다. 이 규칙성을 찾아낸다면 어렵지 않은 문제이다. dragon이라는 배열을 만들어서 i번째에 드래곤커브 i의 방향변화를 모두 넣어주면된다. 즉 dragon[i]의 원소의 개수는 (2^드래곤세대)라고 생각하면 된다. dragon[i]에 위의 규칙성을 따라서 방향을 모두 넣어주었으면, 이제는 시작좌표를 기점으로 해당 방향을 더해가면서 100*100의 범위안에만 있으면 그 좌표값을 True로 바꿔주면된다. True로 바꿔주는 것이 편한 이유는 나중에 네꼭짓점이 모두 드래곤커브의 한점인지 판단할때의 조건문에서 별도의 등가비교 필요없이 해당좌표값만 적어주면되기 때문이다.  

 

5) 구현코드   

#방향 0-1-2-3
dx=[1,0,-1,0]
dy=[0,-1,0,1]

n=int(input())
info=[list(map(int, input().split())) for _ in range(n)] #드래곤커브정보 
dragon=[[] for _ in range(n)] #드래곤커브 방향 배열 

#드래곤 커브 방향 조사해주기 
for i in range(n):
  x,y,d,g=info[i] #시작좌표, 시작방향, 세대 
  dragon[i].append(d) #시작방향 
  for _ in range(g):#세대수만큼
    #여태까지의 방향 반대로 
    reverse_d=list(reversed(dragon[i])) 
    #돌면서 1 더한값 추가해주기 
    for d in reverse_d:
      if d+1==4: #3 다음방향은 0 
        dragon[i].append(0)
      else:
        dragon[i].append(d+1)

#드래곤커브가 지나간 길 
arr=[[False]*101 for _ in range(101)]

#드래곤 커브 좌표 표시해주기 
for i in range(n):
  x,y,d,g=info[i]
  arr[y][x]=True
  for d in dragon[i]:
    x,y=x+dx[d],y+dy[d] #방향따라 이동한 좌표
    #범위안에 들어오면 
    if 0<=x<=100 and 0<=y<=100:
      arr[y][x]=True #꼭짓점 추가 

cnt=0
#네 꼭짓점이 모두 드래곤커브의 일부인것 구하기 
for i in range(100):
  for j in range(100):
    #네 꼭짓점이 모두 True
    if arr[i][j] and arr[i+1][j] and arr[i][j+1] and arr[i+1][j+1]:
      cnt+=1 
print(cnt)

 

⭐️난이도:  골드 4⭐️

https://www.acmicpc.net/problem/15685

15685번: 드래곤 커브