하노이타워(재귀)

1. 하노이 타워 문제

하노이 타워 문제는 재귀함수의 대표적인 예로 꼽힌다.

하나의 막대에 쌓여 있는 원반을 다른 하나의 원반에 그대로 옮기는 방법에 관한 것이다.

막대가 3개인 이유는 제약조건이 있기 때문이다.

2. 제약조건

원반은 한 번에 하나씩만 옮길수 있다.

그리고 옮기는 과정에서 작은 원반의 위에 큰 원반이 올려져서는 안된다

따라서 막대 B의 도움이 필요하다.

3. 문제 해결

원반의 수가 늘어나도 위 해결 과정처럼 해결방법은 똑같다. 일련의 과정을 더 많이 반복할 뿐 이다.

그래서 위 해결과정에서 반복의 패턴을 찾아야 한다.

먼저 처음 3번 원반을 C로 옮기려면1번과2번 막대를 B에다 옮기는 방법에 대해 고민해야한다.

이것이 하노이타워 문제해결의 핵심이다.

1번과 2번만 B로 옮기면 3번 원반을 C로 옮기는것은 간단하기 때문이다.

다음 4개의 원반을 대상으로 생각을 확장해보자

마찬가지로 4번 원반을 C로 옮기려면 1,2,3번 원반을 B로 옮겨야 한다.

그러면 4번 원반을 막대 C로 간단히 옮길 수 있다. 그리고 B에 남겨진 1,2,3번 원반을 C로 옮기는 과

정은 이전 앞서본 세 개의 원반을 다른 막대로 옮기는 과정과 같다.

4. 일반화

이를 일반화해서 막대 A에 꽃혀있는 원반 N개를 C로 옮기는 과정을 정리해보겠다.

1. 작은 원반 N-1개를( 맨 아래의 원반을 제외한 나머지 원반을) A에서 B로 이동

2. 큰 원반( 맨 아래의 원반 ) 1개를 A에서 C로 이동

3. 작은 원반( 위의 1단계에서 옮겨진 원반 ) N-1개를 B에서 C로 이동

이렇듯 원반 N개를 이동하는 문제는 원반 N-1개를 이동하는 문제로 세분화되고, 또 원반 N-1개

를 이동하는 문제는 원반 N-2개를 이동하는 문제로 세분화 된다.  즉 원반 N개를 이동하는 문제

는 결국 원반 1개를 이동하는 매우 쉬운 문제로 세분화되는 것이다.

5. 코드

public class b_05_HanoiTowerSolu {
                            //from에 꽃혀있는 num개의 원반을 by를 거쳐서 to로 이동 
    static void HanoiTowerMove(int num, char from, char by, char to)
    {
        if(num==1)    // 이동할 원반의 수가 1개라면
        {
            System.out.printf("원반1을 %c에서 %c로 이동 \n", from, to);
        }
        else
        {   
            HanoiTowerMove(num-1, from, to, by);// 3단계 중 1단계 
            System.out.printf("원반%d을(를) %c에서 %c로 이동 \n", num, from, to);// 3단계 중 2단계
            HanoiTowerMove(num-1, by, from, to);// 3단계 중 3단계
        }
    }
    public static void main(String[] args) {
        // 막대A의 원반 3개를 막대B를 경유하여 막대C로 옮기기
        HanoiTowerMove(3, 'A', 'B', 'C');
}
}

원반1을 A에서 C로 이동 
원반2을(를) A에서 B로 이동 
원반1을 C에서 B로 이동 
원반3을(를) A에서 C로 이동 
원반1을 B에서 A로 이동 
원반2을(를) B에서 C로 이동 
원반1을 A에서 C로 이동