[G5] 백준 11729 - 하노이 탑 이동 순서 (Python3)

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

---

풀이 아이디어

재귀적인 방법을 사용하여 하노이 탑 문제를 해결합니다. 첫 번째 장대에 있는 원판들을 세 번째 장대로 옮기는 과정에서 아래의 과정을 반복한다.

1. n-1개의 원판을 두 번째 장대로 옮긴다.
2. 가장 큰 원판을 첫 번째 장대에서 세 번째 장대로 옮긴다.
3. 두 번째 장대에 있는 n-1개의 원판을 세 번째 장대로 옮긴다.

초기 상태의 가장 큰 원판을 목표하는 곳(세 번째 장대)으로 옮기고나면, 다시 두 번째 장대의 n-1개의 원판을 첫 번째 장대로 옮겨서 n-1번째로  큰 원판을 세 번째로 옮긴다.

풀이👀

1. 재귀 함수 hanoi_tower를 정의한다. 이 함수는 매개변수로 원판의 개수 n, 출발지 기둥 frm, 보조 기둥 tmp, 목표 기둥 to를 받는다.
2. 만약 n이 1이면, 즉 옮겨야 할 원판이 하나라면 해당 원판을 출발지 기둥에서 목표 기둥으로 옮긴다.
3. 그렇지 않은 경우에는 다음과 같이 수행한다.
   • hanoi_tower(n-1, frm, to, tmp): 가장 큰 원판을 제외한 나머지 원판들을 보조 기둥으로 옮긴다.
   • print(frm, to): 원판의 움직임을 출력한다. (출발지, 도착지)
   • hanoi_tower(n-1, tmp, frm, to): 보조 기둥에 있는 원판들을 목표 기둥으로 옮긴다.
4. 이동 횟수는 2의 거듭제곱에서 1을 뺀 값과 같으므로 2**N - 1을 출력합니다.

---

코드🐱‍👓

def hanoi_tower(n, frm, tmp, to):
    if n == 1:
        print(frm, to)
    else:
        hanoi_tower(n-1, frm, to, tmp)
        print(frm, to)
        hanoi_tower(n-1, tmp, frm, to)

N = int(input())
print(2**N - 1)
hanoi_tower(N, '1', '2', '3')