🗼Tower of Hanoi

intro

🗼 유명한 '하노이의 탑' 알고리즘에 대해 소개한다. 3개의 기둥이 있고, 다양한 크기의 n개의 원판(원판의 크기는 모두 다르다)이 존재한다. 퍼즐을 시작하기 전에는 한 기둥에 n개의 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다. 아래 3가지 조건을 만족 시키면서 다른 기둥으로 옮겨서 다시 쌓는 퍼즐이다.

 

① 한 번에 1개의 원판만 옮길 수 있다.

② 가장 위에 있는 원판만 이동할 수 있다.

③ 큰 원판이 작은 원판 위에 있어서는 안된다.

 

이 때, 최소 이동횟수로 맨 왼쪽 기둥에서 맨 오른쪽 기둥으로 n개의 원판을 순서에 맞추어서 쌓아주면 된다

example demo (n=3)

🗼 n=3일 때 Hanoi Tower를 쌓아보자!

🗼 Hanoi Tower 문제는 크게 아래 3가지 순서로 진행된다.

* Hanoi(3,A,C,B): 3개의 원반을 A에서 C까지 (B를 거쳐) 옮기는 과정

 

① 1번부터 4번까지의 과정 = Hanoi(2,A,B,C)

: 먼저 맨 아래 N번의 원반을 제외하고 (N-1)개의 원반을 A에서 바로 옆 B로 옮긴다

 

② 5번 과정

: A에 있는 N번 원반을 C로 옮긴다

 

③ 6번부터 8번까지의 과정 = Hanoi(2,B,C,A)

: B에 있는 (N-1)개의 원반을 C로 옮긴다

 

* 위 3가지 과정을 그림으로 나타내면 아래와 같다.

recursion & code

🗼 따라서 Hanoi(3,A,C,B)는 아래와 같이 나타낼 수 있다.

(이 때, move(N,1,3)은 N번 원반을 1번에서 3번 기둥으로 옮기는 것을 뜻함)

 

Hanoi(3,A,C,B) = Hanoi(2,A,B,C) + Hanoi(1,A,C,B) + Hanoi(2,B,C,A)

 

🗼 일반화한다면

 

Hanoi(N,A,C,B) = Hanoi(N-1,A,B,C) + Hanoi(1,A,C,B) + Hanoi(N-1,B,C,A)

☞ Hanoi(N,start,dest,via) = Hanoi(N-1,start,via,dest) + Hanoi(1,start,dest,via) + Hanoi(N-1,via,dest,start)

(if N == 1 then move 1 plate to dest and return)

 

: "Hanoi(N,A,C,B) = N-1개의 원반을 먼저 A에서 B로 옮기고, 남은 N번째 원반을 C로 옮긴 뒤, B에 있는 N-1개의 원반을 C로 옮긴다"

 

🗼파이썬 코드를 아래와 같이 나타낼 수 있다. 3개의 원반이 옮기는 과정을 출력.

ans=[]
def hanoi(n,a,c,b):
    if n == 1:
        ans.append((a,c))
    else:
        hanoi(n-1,a,b,c)
        hanoi(1,a,c,b)
        hanoi(n-1,b,c,a)

hanoi(3,1,3,2)

for x in ans:
    print(*x)
        
'''
1 3
1 2
3 2
1 3
2 1
2 3
1 3
'''

number of moves

🗼N개의 원반을 하노이 탑에서 움직이는 횟수를 hanoi(N)이라 하자

 

hanoi(N) = hanoi(N-1) + 1 + hanoi(N-1)

(N==1이라면 hanoi(1) = 1)

 

: hanoi(N)을 a_n이라 하면 아래 그림에 의해 hanoi(N) = 2^n - 1

exercises

★ <BOJ G5 11729 하노이 탑 이동 순서> ★

Q. N개의 원판의 하노이 탑 이동 순서 차례대로 출력(하노이 탑 위 예제 코드와 동일). 이동 횟수는 2^N-1로 출력 

 

★ <BOJ G5 1914 하노이 탑> ★

Q. 위 11729 문제와 동일

 

★ <BOJ G4 23250 하노이 탑 K> ★

Q. K번째 이동을 출력. 이 때 시간초과 방지를 위해 선택적으로 재귀 활용. N개의 원판이라면 첫 hanoi() 함수는 (2^(n-1)-1) 횟수 이하일 때만, 두번째 단독 이동은 2^(n-1)번째 이동. 두 번째 hanoi() 함수는 2^(n-1)+1 ~ 2^(n)-1 번째 이동일 때만, 재귀 돌린다. 

 

★ <BOJ S2 15500 이상한 하노이 탑> ★

Q. 기존 하노이 탑은 원판 순서대로 막대에 위치해 있어야 하나, 원판 순서대로 있을 필요 없는 변형된 하노이 탑 문제. 최소 이동 횟수는 그저 당장 가장 무게가 많이 나가는 원판을 찾을 때까지 시뮬레이션으로 바꾼 횟수. pop() + append() 반복하고 찾으면 pop()한 뒤 세번째 최종 막대에 append(). stack + simulation으로 그저 풀리는 문제.

+ printing disk number

🗼 앞서 학습한 하노이의 탑 재귀 알고리즘에서 이동하는 막대의 종류(이전/이후)를 출력하는 것 외로 맨 위부터 작은 순서대로 1번, 2번, 3번 이렇게 N번까지 번호를 매겼을 때, 몇 번의 원판이 이동하는 지 disk number도 도중에 확인할 수 있다.

 

★ hanoi 재귀 코드를 직관적으로 보면 else문에서의 move는 N번 원판을 옮기고(2~N번) / if문에서의 move는 재귀 종료 처리를 위해 마지막으로 남은 1번 원판을 옮기는(1번), 두 종류의 move로 분석할 수 있다.

 

★ 따라서 두 종류의 move(N번 원반 옮기는 move는 (N,출발지점,도착지점)을 ans에 append / 1번 원반 옮기는 move(재귀 종료용)는 (1,출발지점,도착지점)을 ans에 append) 

ans=[]
def hanoi(n,a,c,b):
    if n == 1:
        ans.append((1,a,c))
    else:
        hanoi(n-1,a,b,c)
        ans.append((n,a,c))
        hanoi(n-1,b,c,a)

n=int(input())
print(2**n-1)
hanoi(n,1,3,2)
for pair in ans:
    n1,n2,n3=pair[0],pair[1],pair[2]
    n2='XABC'[n2]
    n3='XABC'[n3]
    print(f'move disk {n1} {n2}->{n3}')

 

---

하노이의 탑 wiki

hanoi(N) 증명 과정