사실 프로그래밍을 처음 공부하는 분이 하노이 탑 문제를 푸는 것은 거의 불가능에 가깝지만, 재귀 함수를 공부하는 데 필수적으로 사용되는 고전 예제입니다. 재귀 함수를 간단히 알아보고 하노이 탑 문제를 함께 풀어보겠습니다.

✅재귀 함수란?

수학 시간에 배웠던 팩토리얼을 기억하시나요? n! = n*(n-1)*(n-2)*…*1 라는 공식이었죠. 팩토리얼을 구하는 방법은 ①반복문과 ②재귀 함수 두 가지가 있습니다.

①반복문으로 팩토리얼 구하기

어떤 값이라도 1을 곱하면 변화가 없기 때문에 초깃값은 1로 설정했습니다. 연산자에 따라서 초깃값을 다르게 설정해야 한다는 것을 기억해 주세요.

#함수를 선언합니다.
def factorial(n):
    #변수를 선언합니다.
    output = 1
    #반복문을 돌려 숫자를 더합니다.
    for i in range(1, n+1):
        output *= i
    #리턴합니다.
    return output

#함수를 호출합니다.
print("1!:", factorial(1))
print("2!:", factorial(2))
print("3!:", factorial(3))
print("4!:", factorial(4))
print("5!:", factorial(5))

②재귀 함수로 팩토리얼 구하기

두 번째 방법은 재귀 함수를 사용하는 방법입니다. 재귀란 ‘자기 자신을 호출하는 것’을 의미합니다. 팩토리얼 연산은 아까 보신 것처럼 n! = n*(n-1)*(n-2)*…*1 으로 표현할 수 있지만, 다음과 같이 표현할 수도 있습니다.

factorial(n) = n*factorial(n-1) (n >= 1 일 때)
factorial(0) = 1

이와 같은 재귀 표현을 이용하여 factorial(4)를 구하는 방법은 다음과 같습니다.

factorial(4) = 4*factorial(3)
    = 4*3*f(2)
    = 4*3*2*factorial(1)*factorial(0) #factorial(0)은 1이므로 곧바로 1로 변경합니다.
    = 4*3*2*1*1

쉽게 이해되시죠? 이를 코드로 나타내면 다음과 같습니다.

#함수를 선언합니다.
def factorial(n):
    #n이 0이라면 1을 리턴
    if n == 0:
        return 1
   
    #n이 0이 아니라면 n*(n-1)!을 리턴
    else:
        return n*factorial(n-1)

#함수를 호출합니다.
print("1!:", factorial(1))
print("2!:", factorial(2))
print("3!:", factorial(3))
print("4!:", factorial(4))
print("5!:", factorial(5))

✅하노이 탑

이제 재귀 함수를 연습할 수 있는 유명한 문제인 하노이 탑 문제에 도전해 보세요. 하노이 탑은 다음과 같은 3개의 기둥과 크기가 다른 원판들이 원뿔 형태로 존재합니다. 이때 다음 규칙을 지켜 원판을 다른 기둥으로 옮겨야 합니다.

1. 한 번에 한 개의 원판만 옮길 수 있습니다.
2. 큰 원판이 작은 원판 위에 있어서는 안 됩니다.

기본적으로 원판의 개수가 n개일 때 2n-1회 움직여야 원판을 모두 옮길 수 있다고 알려져 있습니다. 원판 개수가 4개일 때 어떻게 원판을 옮겨야 하는지 출력하는 프로그램을 구현해 보세요.

#출력 결과 예시

원판의 개수를 입력하세요: 4
A탑 → C탑
A탑 → B탑
C탑 → B탑
...생략...
A탑 → C탑
A탑 → B탑
C탑 → B탑

힌트를 조금 드리자면, 하노이 탑에는 3개의 기둥이 있습니다. 각각의 기둥을 A, B, C라고 표현하겠습니다. 그리고 ‘처음 원판이 있는 기둥’을 ‘시작 기둥’, ‘원판을 옮겨야 하는 기둥’을 ‘대상 기둥’, ‘보조적으로 활용하는 기둥’을 ‘보조 기둥’이라고 하겠습니다.

일단 원판이 하나일 때는 “시작 기둥”에서 “대상 기둥”으로 원판을 옮기기만 하면 됩니다.

코드로 옮긴다면, 다음과 같겠죠?

if 원판이 1개:
    이동 from 시작기둥 to 대상기둥

시작 기둥이 “A”이고, 대상 기둥이 “B”라면 위 코드를 다음과 같이 출력됩니다.

A탑 → B탑

이어서 원판이 2개일 때는다음과 같은 과정에 따라서 ①위에 있는 원판을 “보조 기둥”으로 옮기고 ②아래에 있는 원판을 “대상 기둥”으로 옮긴 뒤 ③”보조 기둥”에 있던 원판을 “대상 기둥”으로 옮기면 ④모든 원판이 “대상 기둥”으로 옮겨집니다.

이제 조금 확장해서 생각해 보겠습니다. 다음 그림과 같이 원판 하나와 원판 덩어리가 있는 경우 아래에 있는 원판을 “시작 기둥”에서 “대상 기둥”으로 옮기려면 어떻게 해야 할까요?

①일단 덩어리를 “보조 기둥”으로 옮깁니다. ②이어서 아래의 원판을 “대상 기둥”으로 옮깁니다. ③”보조 기둥”에 있던 덩어리를 “대상 기둥”으로 옮깁니다. ④모든 원판이 “대상 기둥”으로 옮겨집니다.

그림을 코드로 옮기면 다음과 같습니다.

if 원판이 2개 이상
    덩어리 이동 from 시작기둥 to 보조기둥
    이동 from 시작기둥 to 대상기둥
    덩어리 이동 from 보조기둥 to 대상기둥

그리고 이전과 마찬가지로 시작 기둥에서 대상 기둥으로 이동을 출력하면 됩니다.

이동 from 시작기둥 to 대상기둥

A탑 → B탑

그렇다면 “원판이 2개 이상인 덩어리 이동”은 어떻게 표현해야 할까요? 원판의 덩어리도 하나의 하노이 탑 문제입니다. 따라서 함수를 재귀 호출하면 됩니다. 알고리즘을 전체적으로 한글로 풀어서 적어보면 다음과 같습니다.

무척 어렵지만 한글 알고리즘을 생각해낼 수 있다면 하노이 탑 문제를 해결할 수 있습니다. 한글 알고리즘이 어떻게 나왔는지 그림과 비교해 보면서 충분히 고민해 보세요. 혼자서 해결이 어렵다면, 아래 해설 강의를 참고하셔서 다시 도전해 보는 것도 좋습니다.

#하노이 탑에서 필요한 요소를 모두 매개변수로 받습니다.
하노이탑(원판, "시작기둥"에서 "대상기둥"으로 "보조기둥"을 활용해서):
    if 원판이 1개:
        이동 from 시작기둥 to 대상기둥

    if 원판이 2개 이상:
        #아래의 원판을 제외하고, 시작 기둥에서 보조 기둥으로 이동합니다.
        하노이탑(원판 -1, "시작기둥"에서 "보조기둥"으로 "대상기둥"을 활용해서)
        이동 from 시작기둥 to 대상기둥

        #아래의 원판을 제외하고, 보조 기둥에서 대상 기둥으로 이동합니다.
        하노이탑(덩어리 -1, "보조기둥"에서 "대상기둥"으로 "시작기둥"을 활용해서)