백준 11729번: 하노이 탑 (Python)

문제

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 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)