소스코드
import sys
input = sys.stdin.readline
N = int(input().strip())
def hanoi(n, start, end, middle):
# 기저조건
if n == 1:
sys.stdout.write(f"{start} {end}")
return
hanoi(n-1, start, middle, end)
sys.stdout.write(f"{start} {end}")
hanoi(n-1, middle, end, start)
sys.stdout.write(f"{2**N - 1}\n")
hanoi(N,1,3,2)
Python
복사
풀이
hanoi(3, 1, 3, 2)
├── hanoi(2, 1, 2, 3)
│ ├── hanoi(1, 1, 3, 2)
│ │ └── print: 1 → 3 ← 출력①
│ └── print: 1 → 2 ← 출력②
│ └── hanoi(1, 3, 2, 1)
│ └── print: 3 → 2 ← 출력③
├── print: 1 → 3 ← 출력④
└── hanoi(2, 2, 3, 1)
├── hanoi(1, 2, 1, 3)
│ └── print: 2 → 1 ← 출력⑤
└── print: 2 → 3 ← 출력⑥
└── hanoi(1, 1, 3, 2)
└── print: 1 → 3 ← 출력⑦
Python
복사
하노이의 탑은 옮기는 원판의 개수가 줄어들어도 문제의 처리 순서와 로직은 동일하다.
1.
가장 큰 원판을 제외한 n-1개의 원판을 임시 장대로 옮긴다
2.
가장 큰 원판을 목적지 장대로 옮긴다
3.
가장 큰 원판을 제외한 n-1개의 원판을 목적지 장대로 옮긴다
n이 더 작은 경우나 더 큰 경우를 생각해보면 좀 더 와닿을 것이다.
hanoi(2, 1, 3, 2)
├── hanoi(1, 1, 2, 3)
│ └── print: 1 → 2 ← 출력①
├── print: 1 → 3 ← 출력②
└── hanoi(1, 2, 3, 1)
└── print: 2 → 3 ← 출력③
Python
복사
n이 2개인 경우도 동일한 패턴을 보이는 것을 잘 보면 찾을 수 있다.
1.
가장 큰 원판을 제외한 1개의 원판을 임시 장대로 옮긴다
2.
가장 큰 원판을 목적지 장대로 옮긴다
3.
가장 큰 원판을 제외한 1개의 원판을 목적지 장대로 옮긴다
흐름은 알겠는데 이걸 재귀함수로 구현을 못 하겠어요
아마 많은 분들이 예시를 적어보며 대충 흐름은 감을 잡았을텐데요, 왜 재귀함수로 구현해야하는지, 인자 구성은 왜 저래야하는지 등에 대해 설명해보겠습니다.
왜 재귀함수여야 할까요?
재귀가 적절한 이유는 다음과 같습니다:
같은 작업을, 더 작은 규모의 작업으로 반복하고 있는 구조이기 때문
위에서도 말했듯이, 하노이의 탑은 n이 작아지든 커지든 핵심 논리는 동일합니다. n=3일 때를 해결하려면, n=2인 위의 두 개의 원판을 먼저 옮겨야하고, n=2일 때를 해결하려면, 마찬가지로 n=1인 하나의 원판을 먼저 옮겨야합니다.
왜 인자 구성이 저렇게 될까요?
•
n : 현재 옮겨야 하는 원판 개수
•
start : 현재 원판이 쌓여 있는 출발 기둥
•
end : 원판을 옮길 목표 기둥
•
temp : 옮기는 도중에 잠깐 놓는 용도의 중간 기둥
재귀함수는 내부에서 재귀적으로 실행될 때, 이전 함수의 정보를 기반으로 실행됩니다. n이 없다면, 우리는 언제 함수를 끝내야하는지 모를 겁니다. start, end, temp는 인덱싱을 이용해 처리하는 방법으로도 가능하지 않을까 싶은데요, 굳이 그렇게 하는 것보다는 인자로 넘겨줘서 내부에서 재귀적으로 실행할 때 편리하게 사용 가능합니다.