재귀 함수 - 하노이의 탑

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 사용해보면서 배운 점을 정리한 글입니다.

PS 문제를 풀다보니 stack 학습 이후 재귀 풀이에 극도로 취약함을 발견하였다. 재귀함수도 근본적으로는 stack 구조라는 점에서 고도화된 문제 풀이를 위해서는 재귀 함수의 이해가 필수라 생각된다. 특히 고난도 문제 풀이에서는 재귀 함수 풀이가 요구되는 경우가 많다... 개중에서도 하노이의 탑은 재귀 함수의 구조를 학습함에 가장 기초적인 문제로 알려져있다. 기본적인 재귀함수를 작성할 수 있으면 곧바로 풀리지만 그렇지 않으면 감도 안잡히거나 시간이 굉장히 오래걸린다. 필자는 감도 안잡혔다. (지금 시점 골드 4...)

하노이의 탑 문제란

하노이의 탑은 수학에서 비롯된 문제로 다음 2가지 조건을 만족한 채 처음 기둥에서 끝 기둥으로 원반을 옮기는 방법 or 횟수를 찾는 문제다.

• 한 번에 옮길 수 있는 원반은 기둥 위의 원반 하나 뿐이다.
• 그 어떤 원반도 그 보다 더 작은 원반 위에 쌓을 수 없다.

이 조건에서 "최소 이동 횟수라는 점을 만족하면서 옮기는 횟수"나 ""최적 경로로 옮겼을 때 원반의 이동 순서"" 등을 문제가 출제된다.

문제 설정

이번 포스팅은 간단하게 A번 기둥에 쌓여있는 1부터 N까지의 원반을 C번 기둥에 옮기는 문제를 해결하기로 한다. 가장 일반적이고 간단한 형태의 하노이의 탑 문제다.

문제 도식화

N=1인 경우 그냥 출발지점에서 경유 없이 도착지점에 원반을 옮기면 된다.

N=2인 경우 N=1 원반을 경유지에 두고 N=2 원반을 도착지점이 경유없이 옮긴 뒤 다시 N=1 원반을 도착지점에 쌓는다.

N=2 까지의 원반들을 우선 도착지점을 경유지 삼아 경유 지점에 쌓아두고 N=3 원반을 경유없이 도착 지점에 옮긴 뒤 경유지점에 옮겨둔 N=2 까지의 원반들을 출발지점을 경유지 삼아 도착지점에 옮겨서 마무리한다.

문제 분해

재귀 함수는 더 작은 차원으로 문제를 쪼개서 특정 종결 조건에 다다르면 결과를 반환함으로써 결과들을 취합해 최종 결과값을 받는 함수이므로 문제를 어떻게 분해할 지 고민해야 한다.

종결 조건

재귀함수의 가장 낮은 차원을 결정해야 한다. 여기서는 가장 작은 원반인 1이 이동한 경우다.

재귀식 설계

종결조건을 설정했으니 일반항 N에 대해 어떻게 이전항의 조합으로 표현할 지 고민해야 한다.

N=2의 경우 1이 경우지점에 갔다가 2가 도착지점 C에 가고 1이 도착지점 C로 이동하는 3단계로 완성된다.

N=3의 경우 1, 2번 원판이 경유지점 B에 갔다가 3이 도착지점 C에 가고 1, 2번 원판이 도착지점 C로 이동하는 3단계로 완성된다.

즉, 이 문제는 N-1번까지의 원판이 경유지점 B에 가는 방법 + N번 원판이 도착 지점 C에 가는 방법 + N-1번까지의 원판이 도착지점 C에 가는 방법 3가지로 쪼개진다.

재귀함수 작성

문제를 해결하기 위해 필요한 정보는 원반 번호 n, 출발지 start, 경유지 via, 도착지 to 4가지이다. 즉, 함수로 정의하면 hanoi(N:int, start:str, via:str, to:str)로 표현할 수 있고 분해된 문제들을 재귀식에 대입하면 hanoi(N-1, start, to, via) + move N A to C + hanoi(N-1, via, start, to)가 될 것이다.

def hanoi(N:int, start:str, via:str, to:str):
    if N == 1: # 종결조건: 1번 원반을 움직일 차례인 경우
        print(f'{N} moves {start} to {to}') # 목적지로 이동하며 마무리
    else:
        hanoi(N-1, start, to, via) # N-1까지의 원반들이 경유지로 이동
        print(f'{N} moves {start} to {to}') # N번 원반이 도착지로 이동
        hanoi(N-1, via, start, to) # N-1까지의 원반들이 도착지로 이동

이동 횟수 구하기

이동 경로를 구했으니 이동 횟수는 사실 재귀함수에 매개변수로 횟수를 기록할 변수를 넣고 print문이 호출될 때마다 1을 더해주면 구할 수 있다. 그러나 뭔가 횟수만을 요구했는데 굳이 처음부터 끝까지 저 과정을 반복해야 할까? 재귀로 문제를 쪼갤 수 있다는 건 점화식을 구할 수 있다는 이야기이므로 수열로 나타내서 이동 횟수를 구해보자.

점화식으로 횟수를 나타내면 $a_1=1$, $a_n=a_{n-1}+1+a_{n-1}$로 나타낼 수 있다. 즉, $a_1=1,\ a_n=2\cdot a_{n-1} + 1$이다. 우변의 항의 계수가 2이고 나머지는 상수라는 점에서 좌우변에 똑같은 값을 더해 등비수열의 형태로 만들 수 있을 듯하다. $a_n + 1=2(a_{n-1}+1)$이고 이러면 초항이 2인 등비수열이 된다. $b_n=a_n+1$이라 하면 $b_1=2$이고 $b_n=2\cdot b_{n-1}$인 등비수열이 완성된다. $b_n=2^n=a_n+1$이므로 $a_n=2^n-1$이다. 이를 정수론에서는 메르센 수라고도 말한다.(알고만 있자!)

이제 일반식을 구했으니 굳이 하노이의 탑 문제에서 원반의 움직임을 추적할 필요 없이 N개의 원반을 목적지로 이동하는데 필요한 최소 횟수는 $2^N - 1$임을 확인할 수 있었다.

관련 문제

하노이 탑 이동 순서