[BOJ][Python]하노이 탑 이동 순서 #11729

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

📌풀이

내가 쓴 풀이(성공)

• hanoi: 원판 이동을 위한 재귀 함수
  • 마지막 판을 제외하고, 모든 판이 중간 봉으로 이동해야 함
  • 이후, 마지막 판을 시작 봉에서 도착 봉으로 이동
  • 중간 봉을 시작 봉으로 고려하고, 비어있는 시작 봉을 중간 봉으로 고려하여 다시 hanoi 실행
  • 중간의 원판 이동 결과를 저장하기 위해 global 리스트 cnt 활용

def hanoi(start, middle, target, n):
    global cnt
    
    if n > 0:
        hanoi(start, target, middle, n-1) # 마지막 원판 제외 중간봉으로 이동
        cnt.append([start, target]) # 마지막 판 이동
        hanoi(middle, start, target, n-1) # 나머지를 목표지점으로 이동
        
        
n = int(input())
cnt = []
hanoi('1', '2', '3', n)
print(len(cnt)) # 전체 이동 횟수 출력
for i in range(len(cnt)):
    print(*cnt[i]) # 판 이동 경로 출력

📌후기

이전에 구현해본 적 있는 하노이의 탑이지만, 다시 구현하려니 조금 헷갈리는 부분이 없지않아 있었지만, 다행히 잘 해결할 수 있었다.