하노이의 탑 알고리즘 (with Java)

하노이의 탑

 

원반이 n개인 하노이 탑이 어떻게 이동되는지 몇번 이동하는지 구해보자

 

 

조건

하노이의 탑은 위 그림과 같이 크기 가 다른 원반이 한 기둥에 놓여져 있고 

원반을 모두 왼쪽에서 오른쪽으로 옮겨야 한다.

원반은 큰 것이 아래로 가게 쌓아야 하며 작은 원반 위에 큰 원반이 올 수 없다.

원반을 옮길 때에는 가장 위에 쌓여있는 원반 부터 옮겨야 한다.

 

탑은 3개로 고정하고 원판(disk)의 개수를 입력받아 원판의 옮겨지는 횟수를 출력

public class PracticeMain {
    static int count = 0;
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);

        int number = scanner.nextInt();

        PracticeMain main = new PracticeMain();
        main.moveDisk("1", "2", "3" , number);
        System.out.println("result :" + count);

    }


    public void moveDisk(String first, String center, String last, int number){
        //first : 원반이 있던 탑
        //center : 중간 위치 탑
        //last : 원반들을 옮길 목적지 탑

        if(number == 1){
            ++ count;
            System.out.println(number + " : " + first + " -> " + last);
        } else{
            moveDisk(first, last, center, number -1);
            ++ count;
            System.out.println(number + " : " + first + " -> " + last);
            moveDisk(center, first, last, number -1);
        }
    }
}

 

결과들 ( 원판 이동 횟수 )

 

1개 원판

 

3개 원판