[Algorithm] 재귀 - w. 하노이 탑

지금까지 재귀 문제를 만나면 항상 피하거나, 다른 방법으로 풀려고 노력했던 것 같다.
그러던 중 재귀에 대한 강의를 보고 이 알고리즘을 이해한 것 같아서 정리해보려 한다.
강의 영상 : [바킹독의 실전 알고리즘] 0x0B강 - 재귀

재귀는 절차지향적으로 접근하면 이해할 수 없다!
수학적 귀납법을 생각하며 k번째 단계에 집중해 보자

문제

작년 여름에는 이 문제보다 쉬운 하노이탑 문제도 하루종일 붙들고 있었던 것 같은데, 한번 이해하고 나니까 비슷한 유형의 문제를 계속 풀고싶어졌다!!

우선 원판이 3~5개일 때의 하노이 탑 게임을 손으로 써가며 직접 해결하면서 하노이 탑 게임 규칙에 익숙해졌다.
아직 규칙이 뭔지 명확하게 알지는 못했지만, 어렴풋이 규칙이 있는 게 보였다.

위에서도 말했듯이 재귀는 절차지향적으로 접근하면 안된다! 그래서 원판 하나하나의 이동에 집중하며 그 안에서 순서를 찾으려 했던 과거에는 규칙을 찾기 힘들었던 것 같다.
이번에는 수학적 귀납법을 생각하며 k번째 단계 (k번째 원판)에 집중하려 했다!!

• k번째 원판을 기둥 1 → 기둥 3 으로 이동시키기 위해선
  - 그 위에 있는 1부터 (k-1)개의 원판들을 모두 1→2 로 옮긴 후
  - k번째 원판을 1→3 으로 옮기고,
  - (k-1) 개의 원판을 2→3 으로 이동하면 된다.
  이는 모든 원판에 대해서 성립하는 명제이다.

이 원칙을 유념하며 재귀 문제를 풀어보자!!!

재귀

1. 함수 정의

함수의 역할, 인자 정하기

• 함수의 역할 : (k-1)개의 원판을 기둥 c로 옮기고, k번째 원판을 기둥 b로 옮긴 후에, (k-1)개의 원판을 기둥 b로 다시 옮긴다.
• 함수의 인자 : (k, a, b)
  - k = 옮겨야 하는 원판의 총 개수
  • a = 원판이 현재 놓여있는 위치
  • b = 원판을 옮겨야 하는 목적지

2. base condition

k=1 일 때, 즉, 옮겨야 하는 원판이 1개밖에 없을 때, 원판을 옮기고 함수를 return 한다.

3. 재귀 식

1. k개의 원판을 1→3 으로 옮기기 위해서는

   1. (k-1)개의 원판을 1→2 로 옮기고
   2. 1개의 원판을 1→3 으로 옮기고
   3. (k-1) 개의 원판을 다시 2→3 으로 옮겨야 한다.

2. (k-1) 개의 원판을 1→2 로 옮기기 위해서는

   1. (k-2)개의 원판을 1→3 로 옮기고
   2. 1개의 원판을 1→2 으로 옮기고
   3. (k-2) 개의 원판을 다시 3→2 으로 옮겨야 한다.

3. (k-2) 개의 원판을 1→3 로 옮기기 위해서는

   1. (k-3)개의 원판을 1→2 로 옮기고
   2. 1개의 원판을 1→3 으로 옮기고
   3. (k-3) 개의 원판을 다시 2→3 으로 옮겨야 한다.

3번 과정을 쭉 손으로 써보니 재귀 함수가 명확히 그려졌다.
이 과정을 거쳐 정의한 재귀 함수와 문제 풀이는 다음과 같다.

정답 코드

# 재귀 - 11729번 - 하노이 탑 이동 순서
import sys
input = sys.stdin.readline
n = int(input())
ans = 0
ans_str = []

def hanoi(k, start, end):
    global ans, ans_str
    if k == 1:
        ans_str.append(str(start) + ' ' + str(end))
        ans += 1
        return
    mid = 6 - (start + end)
    hanoi(k - 1, start, mid)
    hanoi(1, start, end)
    hanoi(k - 1, mid, end)

hanoi(n, 1, 3)
print(ans)
print('\n'.join(ans_str))