[11729] 하노이 탑 이동 순서 (재귀)

11729번: 하노이 탑 이동 순서

 

분석

1) 재귀

• 원반이 두 개 이상이면 원반의 개수를 n 이라 할 때,
  1. 가장 아래에 있는 원반 n을 도착 기둥에 옮기기 위해 그 위에 놓여 있는 n-1개의 원반을 보조 기둥에 옮긴다.
  2. 원반 n을 도착 기둥에 옮긴다.
  3. 보조 기둥에 있는 n-1개의 원반을 도착 기둥에 옮긴다.

 

2) 점화식

먼저 "수열 An​= n개의 원판을 이동하는 횟수" 라고 정의하자.
n개의 원판을 이동시키기 위해서는 그 위의 n-1개의 원판을 다른 막대로 이동하고 맨 아래쪽 원판을 도착지로 이동해야 한다.
그리고 다시 n-1개의 원판을 이동해야 하므로 다음과 같은 점화식이 성립한다.
=>  An​ = 2An−1​ + 1

그리고 이를 일반항으로 풀어내면 2ⁿ−1 임을 알 수 있다.

• 위의 점화식을 생각했을 때 결국 n개의 원반을 모두 옮기기 위해서는 2ⁿ−1 번의 이동이 필요
• 시간 복잡도는 O(2ⁿ) 으로 볼 수 있다.

 

풀이

n=int(input())

# 옮길 원반이 현재 있는 출발점 기둥 from_pos
# 원반을 옮길 도착점 기둥 to_pos
# 옮기는 과정에서 사용할 보조 기둥 aux_pos
# 옮기려는 원반의 갯수 n
    
def hanoi(from_pos, to_pos, aux_pos, n):
    if n == 1: # 원반 한 개를 옮기는 문제면 그냥 옮기면 됨
        print(from_pos, to_pos)
        return

    # 원반 n - 1개를 aux_pos로 이동(to_pos를 보조 기둥으로)
    hanoi(from_pos, aux_pos, to_pos, n-1)

    # 가장 큰 원반을 목적지로 이동
    print(from_pos, to_pos)

	# aux_pos에 있는 원반 n-1개를 목적지로 이동(from_pos를 보조 기둥으로)
    hanoi(aux_pos, to_pos, from_pos, n-1)


print(2**n-1) # 하노이탑 이동 횟수
hanoi(1,3,2,n)