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

MEIN_FIGUR·2021년 8월 24일
0

백준_문제풀이

목록 보기
18/21

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]) # 판 이동 경로 출력



📌후기


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

profile
Growing Developer

0개의 댓글