하노이의 탑

하노이의 탑이란?

작은 원반이 위에, 큰 원반이 아래에 위치할 수 있도록 원반을 3개의 기둥 사이에서 옮기는 문제입니다.

모든 원반의 크기는 다르며, 처음에는 모든 원반은 첫번째 기둥에 쌓여져 있습니다.

모든 원반을 세번째 기둥으로 옮기면 되는 문제로 원반은 1개씩만 옮길 수 있고 큰 원반을 작은 원반 위에 쌓을 수 없습니다.

 

기둥 번호를 1,2,3번으로 나타낼때 기둥 번호의 합이 6이므로 시작 기둥, 목표 기둥이 어느 기둥이더라도 중간 기둥은 6-x-y로 구할 수 있습니다.

 

아래와 같은 과정을 재귀로 구현하면 됩니다.

 

1. 바닥 원반을 제외한 원반 그룹을 시작 기둥에서 중간 기둥으로 옮깁니다.

2. 바닥 원반 숫자를 시작 기둥에서 목표 기둥으로 옮겼음을 출력합니다.

3. 바닥 원반을 제외한 원반 그룹을 중간 기둥에서 목표 기둥으로 옮깁니다.

 

아래 그림처럼 동작할 수 있도록 재귀로 구현하면 됩니다.

 

 

 

하노이의 탑 소스 코드

 

https://github.com/jokerKwu/java/blob/master/JavaStructure/src/Hanoi.java