알고리즘
[python]재귀 - 하노이의 탑
ujin2021
2021. 4. 24. 20:40
[참고 블로그]
shoark7.github.io/programming/algorithm/tower-of-hanoi
'하노이의 탑' 이해하기
'하노이의 탑' 문제를 이해하고 문제 해결을 위한 핵심 통찰을 살핀 뒤 코드로 작성합니다. 이후 탑의 개수에 따른 총 이동 횟수를 구하는 일반항까지 수학적으로 유도합니다.
shoark7.github.io
[코드]
# 하노이의 탑 경로출력 - 출처 : https://shoark7.github.io/programming/algorithm/tower-of-hanoi
MSG_FORMAT = "{}: {} -> {}"
def move(N, start, to):
print(MSG_FORMAT.format(N, start, to))
def hanoi(N, start, to, via):
if N == 1:
move(1, start, to)
else:
hanoi(N-1, start, via, to) # 제일 큰 원반을 제외하고 모두 경유지에 쌓는다
move(N, start, to) # 제일 큰 원반을 도착지로 옮긴다
hanoi(N-1, via, to, start) # 경유지에 있던 모든 원반을 다시 도착지로 옮긴다
hanoi(2, 'A', 'C', 'B')
print()
hanoi(3, 'A', 'C', 'B')
print()
hanoi(4, 'A', 'C', 'B')
[설명]
