[Algorythm] 하노이의 탑: 재귀

  하노이의 탑은 특정 기둥에 정렬된 원반을 기존 순서를 지키면서 최소횟수로, 다른 기둥에 옮기는 문제이다. 문제는 여기에 2가지 규칙이 추가된다는 것이다. 

• 한 번에 움직일 수 있는 원반은 단 한가지
• 어떤 원반 위에는 그보다 더 큰 원반이 올라가지 못한다.

  기둥이 3개일 때 그냥 최소횟수를 구하라고 한다면, 한 기둥에 전체 원반을 엎어버리고 그대로 완료기둥에 엎어진 걸 다시 엎는 것으로 쉽게 풀릴 것이다. 그런데 원반 위에는 그보다 더 큰 원반이 올라가지 못한다는 전제가 걸림돌이 된다. 큰 원반구조를 조금이라도 옮기고 싶다면 그 위 작은 원반들을 매 번 산 모양으로 쌓아야 하기 때문이다. 여기서 재귀가 발생한다.

 

  1차적으로 큰 원반만 목표 위치로 옮기는 것은 원반이 두개일 때와 로직이 유사하다. 원반들을 가장 큰 원반과 나머지 원반, 2묶음으로 묶고, 묶음 원반을 다른 기둥에 정렬한 뒤, 드러난 가장 큰 원반을 빈 목표 기둥으로 옮기는 것.

 

 n=3일 때 전체 구조를 보면 가장 큰 원반 1개를 옮기는 이동횟수는 작은 원반 2개를 중간으로 올려 탑을 쌓는 횟수(+3)에 큰원반 이동 횟수를 더해준다(+1). 그리고 그 위에 다시 원반 2개를 올리는 횟수를 더해(+3) 최종적으로 최소 이동횟수(7)를 구한다. 

 

  만약 원반이 4개라면 어떨까? 노란 원반은 위 7번 과정대로 초록원반이 모두 다른 기둥으로 이동해야(+7) 비어있는 목표 기동에 노란 원반이 이동할 수 있을 것이다(+1). 그리고 초록 원반을 노란 원반 위로 정렬시키는 것은 다시 원반이 3개일 때 과정을 반복하는 것이다(+7).

 

  n이 1 증가할 때마다 n-1개 원반을 재정렬하고, 큰 원반을 옮기고, 그 위에 n-1개 원반을 재정렬하는 것을 반복한다는 것을 알 수 있다 (정렬 > 이동 > 재정렬). 같은 방식으로 n-1개 원반 재정렬도 n-2개 원반을 재정렬하는 과정을 포함한다. 그럼 아래와 같은 재귀를 반복하는 것이다.

 

  정리하자면 n번째 원반을 옮기려면 그보다 작은 모든 원반들이 본인보다 작은 원반들을 재귀적으로 재정렬해야 하는 과정을 반복해야 한다. 작은 원반을 쌓아야만 옮기려는 큰 원반이 드러나기 때문이다. 표현식은 다음과 같다.

T(1) = 1

T(2) = T(1) + 1 + T(1)
     = 1 + 1 + 1
     = 3
     
T(3) = T(2) + 1 + T(2)
     = (1 + 1 + 1) + 1 + (1 + 1 + 1)
     = 3 + 1 + 3 = 7
 
###### T(4) ######
 
T(4) = T(3) + 1 + T(3)
      = ((1 + 1 + 1) + 1 + (1 + 1 + 1)) 
       + 1 
       + ((1 + 1 + 1) + 1 + (1 + 1 + 1))
     = 7 + 1 + 7 = 15     
     
T(4) = 2 * T(3) + 1
     = 2 * (2 * T(2) + 1) + 1
     = 2 * (2 * (2 * T(1) + 1) + 1) + 1
     = 2 * (2 * (2 * 1 + 1) + 1) + 1
     = 31

T(4)
   ├── T(3)
   │   ├── T(2)
   │   │   ├── T(1)
   │   │   ├── +1
   │   │   └── T(1)
   │   ├── +1
   │   └── T(2)
   │       ├── T(1)
   │       ├── +1
   │       └── T(1)
   ├── +1
   └── T(3)
       ├── T(2)
       │   ├── T(1)
       │   ├── +1
       │   └── T(1)
       ├── +1
       └── T(2)
           ├── T(1)
           ├── +1
           └── T(1)

 

  아쉽게도 하노이의 탑은 원반이 어느 위치로 이동했는지도 궁금해하는 문제이다. 이 때  n-1번째 원반탑을 재정렬하는 과정에서 시작기둥과 종결기둥이 달라지므로, 점화식도 이를 고려해주어야 한다.

 

  그럼 아래와 같은 두 함수가 나온다.

def move(N, start, to): # n번 원반을 from에서 to로 옮기는 함수
    print(f"{N}번 원반을 {start}에서 {to}로 이동")

# start: 시작, to: 목적, via: 경유
def hanoi(N, start, to, via):  
    if N == 1: # 3
        move(1, start, to)
    else:
        hanoi(N-1, start, via, to) # 작은 원반을 시작지에서 경유지로 이동
        move(N, start, to) # 드디어 큰 원반을 시작지에서 목적지로
        hanoi(N-1, via, to, start) # 작은원반(묶음)을 경유지에서 큰 원반(목적지) 위에 쌓기
    
    

# 실행 과정
hanoi(3, A, C, B)
├── hanoi(2, A, B, C)
│   ├── hanoi(1, A, C, B)
│   │   └── move(1, A → C)
│   ├── move(2, A → B)
│   └── hanoi(1, C, B, A)
│       └── move(1, C → B)
├── move(3, A → C)
└── hanoi(2, B, C, A)
    ├── hanoi(1, B, A, C)
    │   └── move(1, B → A)
    ├── move(2, B → C)
    └── hanoi(1, A, C, B)
        └── move(1, A → C)

 

 

 

 

1. 11729번 하노이의 탑 이동순서

num = int(input())

def move(start, end):
    print(start, end)

def hanoi(num, start, end, via):
    if num == 1:
        move(start, end)
    else:
        hanoi(num-1, start, via, end)
        move(start, end)
        hanoi(num-1, via, end, start)

print(2**num - 1)
hanoi(num, 1, 3, 2)

 

 

 

 

 

 

 

 

 

 

 

참고문헌

https://shoark7.github.io/programming/algorithm/tower-of-hanoi

https://mgyo.tistory.com/185

https://howudong.tistory.com/330