문제
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.
- 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
- 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.
아래 그림은 원판이 5개인 경우의 예시이다.
입력
첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.
출력
첫째 줄에 옮긴 횟수 K를 출력한다.
두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.
내 풀이(안 좋음 아래 풀이 보세요)
1번째 칸에서 2번째 칸으로 길이 N인 타워를 옮기는 과정을 프린트해주는 함수를 hanoi_12(num: int) -> None이라고 정의하였다. 이후 hanoi_13, hanoi_21, ... hanoi_32를 같은 방식으로 정의하여, 총 6개의 함수를 만들었다.
그리고 각 함수별로 재귀식을 적었다. 경우의 수는 2**N - 1이니 잊지 말고 출력해주자.
(경우의 수 계산: A_1 == 1, A_n == 2A_(n-1) + 1 점화식을 풀면 된다. 고등학교 수학.)
연산 속도도 다른 풀이에 비해 짧고, 코드 길이만 길 뿐 뻔해서 가독성도 괜찮은 풀이라고 생각한다. 다만, 아래 풀이를 보고 보면, 조금 멍청해보이긴 하네 ㅎㅎ;;
코드
def hanoi_12(num: int)-> None:
if num == 1:
print("1 2")
else:
hanoi_13(num - 1)
print("1 2")
hanoi_32(num - 1)
def hanoi_13(num: int)-> None:
if num == 1:
print("1 3")
else:
hanoi_12(num - 1)
print("1 3")
hanoi_23(num - 1)
def hanoi_21(num: int)-> None:
if num == 1:
print("2 1")
else:
hanoi_23(num - 1)
print("2 1")
hanoi_31(num - 1)
def hanoi_23(num: int)-> None:
if num == 1:
print("2 3")
else:
hanoi_21(num - 1)
print("2 3")
hanoi_13(num - 1)
def hanoi_31(num: int)-> None:
if num == 1:
print("3 1")
else:
hanoi_32(num - 1)
print("3 1")
hanoi_21(num - 1)
def hanoi_32(num: int)-> None:
if num == 1:
print("3 2")
else:
hanoi_31(num - 1)
print("3 2")
hanoi_12(num - 1)
N = int(input())
print(2**N - 1)
hanoi_13(N)
모범적인 풀이
현재 위치를 from, 옮겨야하는 위치를 to, 들리게 되는 위치를 via라고 하면, 길이 N인 하노이 탑을 옮기는 과정은
from에서 via로 길이 N-1의 하노이 탑을 옮기고,
from에서 to로 원판 N을 옮기고,
via에서 to로 길이 N-1의 하노이 탑을 옮기는 과정이랑 똑같다.
(from은 이미 쓰이는 용어니, 모든 변수 앞에 _을 그어주자.)
코드
def hanoi(num: int, _from: int, _via: int, _to: int) -> None:
if num == 1:
print(_from, _to)
else:
hanoi(num - 1, _from, _to, _via)
print(_from, _to)
hanoi(num - 1, _via, _from, _to)
N = int(input())
print(2**N - 1)
hanoi(N, 1, 2, 3)