2하노이의 탑 풀이

 

아무리 복잡한 문제라도 입력 크기가 작은 간단한 문제부터 차근차근 생각해 보면 아이디어가 떠오르기 마련입니다. 가장 간단한 원반 한 개 문제부터 풀어 보겠습니다. 동전을 한 개 꺼내서 직접 따라 해 보세요.

 

◼︎ 원반이 한 개일 때

1번 기둥에 있는 원반을 3번 기둥으로 옮기면 끝납니다(1 → 3).

그림 6-5 원반을 1에서 3으로 옮김

 

단 한 번 만에 원하는 곳으로 원반을 옮겼습니다.