하노이의 탑 구현

하노이의 탑

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

조건

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

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

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

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

1. 원반이 1개 일때

1번에서 3번으로 옮기면 된다.

2. 원반이 2개 일때

1번 기둥의 맨 위에 있는 원반 하나를 2번 기둥에 옮긴다. ( 1 -> 2 )

1번 기둥의 마지막 남아있는 원반 하나를 3번 기둥에 옮긴다. ( 1 -> 3 )

2번 기둥에 있는 원반 하나를 3번 기둥에 옮긴다. ( 2 -> 3 )

3. 원반이 3개 일때

1. 1번 기둥의 가장 작은 원반 하나를 3번 기둥에 옮긴다. ( 1 -> 3 )

2. 1번 기둥의 중간 원반 하나를 2번 기둥에 옮긴다. ( 1 -> 2 )

3. 3번 기둥의 가장 작은 원반 하나를 2번 기둥에 옮긴다 ( 3 -> 2 )

4. 1번 기둥의 가장 큰 원반을 3번 기둥에 옮긴다. ( 1 -> 3 )

5. 2번 기둥에 가장 작은 원반 하나를 1번 기둥에 옮긴다. ( 2 -> 1 )

6. 2번 기둥에 중간 원반 하나를 3번 기둥에 옮긴다. ( 2 > 3 )

7. 1번 기둥에 가장 작은 원반을 3번 기둥에 옮긴다. ( 1 -> 3 )

총 7번 옮김

4. 원반이 n개 일때

1번 기둥에 있는 n-1개 원반을 2번 기둥에 옮긴다.

1번 기둥에 가장 큰 원반을 3번 기둥으로 옮긴다.

2번 기둥에 있는 n-1개 원반을 3번 기둥으로 옮긴다.

소스코드

package test1;
 
public class Hanoi {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println("n=3");
        MyHanoi myHanoi = new MyHanoi();
        
//        myHanoi.hanoiFunction(3, 1, 2, 3);
        System.out.println("총 옮긴 횟수: "+myHanoi.hanoiFunction(3, 1, 2, 3)); // 2의 n제곱 - 1 = 옮긴 횟수
    }
}
class MyHanoi{
    int count = 0 ;
    int hanoiFunction(int n, int first, int second, int third) { 
        if(n==1){
            System.out.println(first+"->"+third); 
            count++;
            return count;
        }
        hanoiFunction(n-1, first, third, second);  
        System.out.println(first+"->"+third); 
        count++; 
        hanoiFunction(n-1, second, first, third); 
        
        return count;
    }    
}

출력결과

마지막으로 해당 소스를 첨부한다.

Hanoi.java