하노이의 탑

• 작은 원반이 위에, 큰 원반이 아래에 위치할 수 있도록 원반을 3개의 기둥 사이에 옮기는 문제
  • 모든 원반이 규칙에 맞게 첫 번째 기둥에 쌓여있고 이 상태에서 모든 원반을 세 번째 기둥으로 최소의 횟수로 옮겨야 한다.
  • 원반은 1개씩만 옮길 수 있고 큰 원반을 작은 원반 위에 쌓을 수 없다.
• 3개의 기둥을 각각 시작 기둥, 중간 기둥, 목표 기둥이라고 부르고, 가장 큰 원반을 최소의 단계로 목표 기둥으로 옮기려면 가장 먼저 그룹(가장 큰 원반을 제외한 원반들)을 중간 기둥으로 옮겨야 한다.
• 다시 그룹 중에서 가장 큰 원반을 제외한 원반을 그룹으로 보고 같은 방식으로 옮긴다.
• 이 방식으로 반복하여 원반이 N개인 하노이의 탑 문제를 해결할 수 있다.

//하노이의 탑
public class Hanoi {
 
    //no개의 원반을 x번 기둥에서 y번 기둥으로 옮긴다
    static void move(int no, int x, int y) {
        if (no > 1)
            move(no - 1, x, 6 - x - y);
        //기둥 번호의 합이 6이므로 시작/목표 기둥이 어느 기둥이더라도 중간 기둥은 6 - x - y로 구할 수 있다
        
        System.out.printf("원반[%d]을 %d번 기둥에서 %d번 기둥으로 옮김\n", no, x, y);
        
        if (no > 1)
            move(no - 1, 6 - x - y, y);
    }
}