알고리즘 - 하노이 탑(재귀)

문제

https://www.acmicpc.net/problem/11729

하노이 탑 문제는 재귀 알고리즘 유형의 대표적인 문제이다.
재귀 함수(분할 정복) 유형을 풀기 위해서는 중요한 것이 세가지 있다.

1. 완전탐색이 제한 조건 내에서 가능한지 확인한다. 가능하면 완전탐색으로 푼다.
2. 문제를 더 작은 문제로 분할(devide)한다.
3. 더이상 답을 분할하지 않아도 곧장 풀 수 있는 문제(base case)가 되면 답을 구한다.
4. 각 문제에 대한 답을 원래 문제의 답으로 병합(merge)한다.

이 문제도 마찬가지로 더 작은 문제로 분할 하고, base case를 찾은 뒤 재귀 문제에서 중요한 종료 조건을 적용시켜주면 풀 수있다.

알고리즘

1번에 있는 원판이 3번으로 모두 이동하려면 어떻게 해야할까?

1번에 있는 가장 큰 원판이 3번으로 이동하기 위해서는 가장 큰 원판이 밑에 깔려야 함으로 n-1개의 원판이 모두 2번으로 이동해 있어야 가능한 일이다. 이 과정을 식으로 표현 해보면,

1. 가장 큰 원판이 3번으로 가려면 나머지 n-1개가 2번으로 가야함
2. 1에 있는 원판이 3번으로 감
3. 2번에 있는 n-1개가 3번으로 이동해야 함

위 3단계를 거쳐 문제를 분할 할 수 있다.
위를 식으로 표현하면, Hanoi(n) = 2 × Hanoi(n-1) + 1 로 표현 할 수 있다.

그렇다면 위의 1번 단계를 수행하기 위해서는 어떤 단계가 필요한지 살펴보면,
1. n-1개 중 가장 큰 원판이 2번으로 가기 위해서는 나머지 n-2개가 3번으로 가야함
2. 1번에 있는 가장 큰 원판이 2번으로 이동
3. 3번에 있는 n-1개가 2번으로 이동

같은 과정을 반복해 나가는 것을 볼 수 있다.

이렇게 부분 구조를 구했고, 종료 조건은 n == 1일때 ( 하나만 움직이면 될 때) 로 설정해주고 함수를 설계하고, 점화식은 Hanoi(n) = 2 × Hanoi(n-1) + 1이 될 것이다.

총 실행 횟수는

1. 위의 점화식의 양변에 1을 더해 우변을 다음과 같이 묶기
   a[n+1] + 1 = 2(a[n] + 1)

2. a[n+1] + 1을 b[n]으로 치환
   b[n] = a[n] + 1

3. a[n+1] -> b[n] 대입
   b[n] = 2*b[n]
   -> 점화식 완성

4. 첫째항으로 밑 구하기
   b[1] = a[1] + 1 = 2

5. 마무리
   첫째항은 2이고 공비는 2인 공비수열이 된다.
   => b[n] = a[n] + 1 = 2^n(2의 n제곱 이라는 뜻)
   => a[n] = 2^n - 1

이 공식이 원판 이동 횟수이 된다.

코드

위 알고리즘을 사용하여 구현한 코드이다.

import sys
input = sys.stdin.readline
n = int(input())


def recursive(n, x, y):
    if n == 1:
        print(x, y)
        return
    recursive(n-1, x, 6-x-y) #1단계
    print(x, y) #2단계
    recursive(n-1, 6-x-y, y) #3단계
    
print(2**n-1) #실행 횟수
recursive(n, 1, 3)

참고 자료

https://velog.io/@younghoondoodoom/%EB%B0%B1%EC%A4%80-11729-%ED%95%98%EB%85%B8%EC%9D%B4-%ED%83%91-%EC%9D%B4%EB%8F%99-%EC%88%9C%EC%84%9C