[백준] 15685 - 드래곤 커브 [Python(파이썬)]

'삼성 SW 역량 테스트' 기출 문제 입니다. 😀

문제 👉 15685번: 드래곤 커브

1. 문제

1. 이차원 좌표 평면 위에서 드래곤의 커브를 그린다.
2. 드래곤은 세 가지 속성(시작 점, 시작 방향, 세대)을 가진다.
3. K세대 드래곤 커브는 K-1세대 드래곤 커브를 시계 방향으로 90도 회전시킨 다음 K-1세대 드래곤 커브의 끝 점에 붙인 것이다.
4. 다음과 같은 조건을 따른다.
   • 이차원 좌표 : 0 ≤ x, y ≤ 100
   • 드래곤의 시작 방향 : 0 ≤ d ≤ 3
   • 드래곤 커브의 세대 : 0 ≤ g ≤ 10
   • 드래곤 커브의 방향 :
     • 0: x좌표가 증가하는 방향 (→)
     • 1: y좌표가 감소하는 방향 (↑)
     • 2: x좌표가 감소하는 방향 (←)
     • 3: y좌표가 증가하는 방향 (↓)
5. 드래곤 커브는 격자 밖을 벗어나지 않고 서로 겹칠 수 있다.
6. 이차원 좌표 평면에서 네 꼭짓점이 모두 드랜 커브의 일부인 정사각형의 개수를 출력한다.

2. 풀이

시뮬레이션을 이용한 문제 풀이

1. N세대의 선분 개수는 2^N개이다.
2. 10세대의 선분에서 0~2^N까지의 부분이 N세대의 드래곤 커브이다.

3. 코드

B = [[0]*101 for _ in range(101)]
D = {0:(1,0), 1:(0,-1), 2:(-1,0), 3:(0,1)} # 우, 상, 좌, 하
G = [0]
ret = 0

# 10세대 까지의 드래곤 선분 미리 만들기
for i in range(1, 11): 
    k = 2**(i-1)
    for j in range(k):
        G.append((G[k-j-1]+1)%4) # 뒤로 훑으면서 90도 돌려서 저장
# 드래곤 선분 그리기
for _ in range(int(input())):
    x, y, d, g = map(int, input().split()) 
    a[x][y] = 1
    for i in range(2**g): # 세대의 선분 수 만큼
        x, y = x + D[(G[i]+d)%4][0], y + D[(G[i]+d)%4][1] # 주어진 방향을 90도 돌린다
        B[x][y] = 1
# 사각형 개수 구하기
for i in range(100):
    for j in range(100):
        if B[i][j] and B[i+1][j] and B[i][j+1] and B[i+1][j+1]:
            ret += 1
print(ret)

• 결과 : 72 ms
• 다시 풀어봐야겠다... 문제 이해하는게 나만 어려운가... 90도 돌리는게 이해가 안간다... ㅠㅠ

---

References

•  

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋