하노이의 탑은
작은 원반이 위에 큰 원반이 아래에 위치하도록 쌓은 원반을 3개의 기둥 사이에서 옮기는 문제다.
모든 원반은 크기가 다르고 모든 원반은 최초 이 규칙에 맞게 첫 번째 기둥에 쌓여있다.
이 상태에서 규칙에 맞도록 3번째 기둥으로 최소 횟수로 옮기는 것이다.

하노이의 탑 구현하기

하노이의 탑을 구현하는 프로그램을 작성해본다.
물론 재귀호출을 사용하여 프로그램을 작성해본다.

Main Method

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
    
    System.out.println("하노이의 탑");
    System.out.print("원반의 갯수 : ");
    int n = sc.nextInt();
    
    move(n, 1, 3);		// 1번 기둥에 쌓인 n개의 원반을 3번 기둥으로 옮김
}

move

// no개의 원반을 x번 기둥에서 y번 기둥으로 옮김
static void move(int no, int x, int y) {
	if(no > 1) {
    	move(no - 1, x, 6 - x - y);
    }
    
    System.out.printf("원반[%d]을(를) %d번 기둥에서 %d번 기둥으로 옮김\n", no, x, y);
    
    if(no > 1) {
    	move(no - 1, 6 - x - y, y);
    }
}

이 프로그램은 기둥 번호를 정수 1,2,3으로 표현한다. 기둥 번호의 합이 6이므로 시작기둥, 목표기둥이 어느 기둥이더라도 중간 기둥은 "6-x-y"로 구할 수 있다.

move 메서드의 흐름을 보면 아래와 같다. 매개변수 no가 3일 경우로 가정하자.