3. 2 하노이 타워

재귀 알고리즘 중에 하노이 타워가 있습니다.

하노이 타워 알고리즘은 n 개의 돌을 이동시키는 문제입니다. 세 개의 기둥이 있고 하나의 기둥에 n 개의 돌이 크기 순으로 있습니다. 한 번에 하나의 돌을 이동할 수 있고 작은 돌 위에 큰 돌이 올 수 없습니다. 이와 같은 규칙을 이용하여 n 개의 돌이 있는 기둥에서 다른 기둥으로 모든 돌을 옮기는 문제입니다.

이 문제를 재귀적으로 해결하면 다음과 같은 방법으로 해결할 수 있습니다.

가정: n-1개의 돌을 옮길 수 있다.

가정에 의해 먼저 A에 있는 n-1개의 돌을 C를 이용하여 B로 옮깁니다.

규칙에 의해 1개의 돌을 A에서 C로 옮깁니다.

가정에 의해 B에 있는 n-1개의 돌을 A를 이용하여 C로 옮깁니다.

따라서 n개의 돌을 옮길 수 있다.

이를 의사코드(pseudo code)로 나타내면 다음처럼 표현할 수 있습니다. 탈출 조건을 표현하고 있음을 확인하세요.

Hanoi(src, use, dest, n)

조건 n<=0

종료

    Hanoi(src,dest,use,n-1)

    Move(src,dest)

    Hanoi(use,src,dest,n-1)

알고리즘을 보면 재귀 호출 전보다 n은 1 감소하고 n이 1이 되면 재귀를 탈출하므로 탈출 조건에 근접함을 알 수 있습니다.