5-3. 하노이의 탑(Tower of Hanoi)

: 쌓아 놓은 원반을 최소의 횟수로 옮기기 위한 알고리즘

 

 

 

・하노이의 탑

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

모든 원반은 크기가 다르고 처음에는 모든 원반이 이 규칙에 맞게 첫 번째 기둥에 쌓여 있다. 이 상태에서 모든 원반을 세 번째 기둥으로 최소의 횟수로 옮기면 된다. 원반은 1개씩만 옮길 수 있고 큰 원반을 작은 원반 위에 쌓을 수 없다.

 

key. 가장 먼저 맨 아래 원반을 제외한 나머지 원반을 중간 기둥으로 옮겨야 한다.

 

 

 

[소스코드]

static void move(int no, int x, int y) {
        if(no > 1)
            move(no - 1, x, 6 - x - y);
        
        System.out.println(
                "원반 [" + no + "]을 " + x + "기동에서 " + y + "기둥으로 옮김"
                );
        
        if(no > 1)
            move(no - 1, 6 - x - y, y);
    }