알고리즘 기초 - 하노이의 탑(Tower of Hanoi)

🌈 하노이의 탑(Tower of Hanoi)

🔥 하노이 탑 문제 설명

🔥 하노이 탑 문제 과정

🔥 핵심 아이디어 정리

🔥 재귀 호출 과정 요약

🔥 하노의 탑 최종 코드

1. 하노이 탑 문제 설명

• 하노이의 탑은 프랑스 수학자 에두아르드가 처음으로 발표한 게임입니다. 하노이의 탑은 A, B, C 3개의 기둥과 기둥에 꽂을 수 있는 N개의 원판으로 이루어져 있습니다. 이 게임에서 다음의 규칙을 만족해야 합니다.
  • 1. 처음에 모든 원판은 A기둥에 꽂혀 있다.
  • 2. 모든 원판의 지름은 다르다.
  • 3. 이 원반은 세 개의 기둥 중 하나에 반드시 꽂혀야 한다.
  • 4. 작은 원반 위에 큰 원반을 놓을 수 없다.
  • 5. 한 번에 하나의 원판(가장 위에 있는 원판) 만을 옮길 수 있다.
• 이 규칙을 만족하며 A기둥에 있는 원반 N개를 모두 C 원반으로 옮기고 싶습니다.
  모든 원반을 옮기기 위해 실행되어야 할 최소 원반 이동 횟수를 계산하는 프로그램을 완성해주세요.
• 즉, 세개의 기둥(A,B,C)가 있다고 가정할 때, A->C로 모든 원판을 옮겨야하고, 원판의 지름은 모두 다른데 작은 원판이 큰 원판보다 아래 머무르지 않게 하며 이동시키는 것
• 원판이 n개 일 때, 최소 이동 횟수 공식 : (2**n) -1
• 시간복잡도 : O(2^n)

2. 하노이 탑 문제 과정

1. 원판이 1개 일 때(n=1),

• 시작 기둥(A)에서 목표 기둥(C)로 바로 이동시키면 됨
• 이동 경로는 [A,C]이며, 이동 횟수는 1회임

res = [] # 원판이 이동하는 경로
def func(n, 첫기둥, 목표기둥, 중간기둥):
    if n == 1:
        res.append([첫기둥, 목표기둥]) # 첫기둥에서 목표기둥으로 이동
        return None
func(1, 'A', 'C', 'B')        

• 함수호출 과정 : func(1, 'A', 'C', 'B')

2. 원판이 2개 일 때(n=2),

• 맨위에 있는 원판 1개를 시작기둥(A)에서 보조기둥(B)로 잠시 이동시킨 다음, 하나 남은 원판을 목표기둥(C)로 이동
  • 원판이 2개 이상일 때에는 n-1개의 원판을 시작기둥(A)에서 중간기둥(B)로 옮김
  • ⭐️ func(n, 첫기둥, 목표기둥, 중간기둥) → func(n-1, 첫기둥, 중간기둥, 목표기둥)
• 이후, 보조기둥(B)에 있는 원판 1개를 목표기둥(C)에 옮기면 A에서 C로 모두 이동됨
• 이동 경로는 [A,B] ⇢ [A,C] ⇢ [B,C] 이며, 이동 횟수는 3회임

res = [] # 원판이 이동하는 경로
def func(n, 첫기둥, 목표기둥, 중간기둥):
    if n == 1:
        res.append([첫기둥, 목표기둥]) # 첫기둥에서 목표기둥으로 이동 : [A-B], [B-C]
        return None
    func(n-1, 첫기둥, 중간기둥, 목표기둥)
    # func(2, 'A', 'C', 'B')
    res.append([첫기둥, 목표기둥]) # 첫기둥에서 목표기둥으로 이동 : [A-C] 
    func(n-1, 중간기둥, 목표기둥, 첫기둥) # func(1, 'B', 'C', 'A') 호출     
func(2, 'A', 'C', 'B') 

• 함수호출 과정
  • 시작 호출 : func(2, 'A', 'C', 'B')
  • 첫번째 재귀식 호출 : func(1, 'A', 'B', 'C') 👈 [A-B] 출력 & return(종료)
  • return 되었기 때문에 func(2, 'A', 'C', 'B')로 돌아옴
  • res.append([첫기둥, 목표기둥]) 실행 👈 [A-C] 출력
  • 두번째 재귀식 호출 : func(1, 'B', 'C', 'A') 👈 [B-C] 출력 & return(종료)

3. 원판이 3개 일 때(n=3),

• 가장 작은(맨 위에 있는 원판) 1개를 시작기둥(A)에서 목표기둥(C)로 잠시 이동시킨 다음, 두번째로 작은(두번째 있던 원판)을 원판을 보조기둥(B)로 이동
• 목표기둥(C)에 있는 가장 작은 원판을 보조기둥(B)로 이동
  • 원판이 2개 이상일 때에는 n-1개의 원판을 시작기둥(A)에서 중간기둥(B)로 옮김
  • ⭐️ func(n, 첫기둥, 목표기둥, 중간기둥) → func(n-1, 첫기둥, 중간기둥, 목표기둥)
• 이후, 가장 큰 마지막 원판 1개를 목표기둥(C)에 옮기면 시작기둥(A)는 빈 상태
  • ⭐️ res.append([첫기둥, 목표기둥])
  • 이때, C에 가장 큰 원판이 이동되었기 때문에 C에 있는 원판 1개는 움직일리 없음
  • ⭐️ 즉, C에 있는 원판을 버렸다고 쳤을 때, 보조기둥(B)와 시작기둥(A)를 swap하면 원판이 2개 있을 때 이동시키는 최초 상황과 같아짐
  • ⭐️ func(n, 첫기둥, 목표기둥, 중간기둥) → func(n-1, 중간기둥, 목표기둥, 첫기둥)
• 보조기둥(B)에서 가장 작은 원판을 시작기둥(A)로 옮긴 뒤, 보조 기둥(B)에 있는 두번째로 작은 원판을 목표기둥(C)로 옮김
• 이동 경로는 [A,C] ⇢ [A,B] ⇢ [C,B] ⇢ [A,C] ⇢ [B,A] ⇢ [B,C] ⇢ [A,C]이며, 이동 횟수는 7회임

res = [] # 원판이 이동하는 경로
def func(n, 첫기둥, 목표기둥, 중간기둥):
    if n == 1:
        res.append([첫기둥, 목표기둥]) # 첫기둥에서 목표기둥으로 이동 : [A-C], [C-B], [B-A], [A-C]
        return None  
    func(n-1, 첫기둥, 중간기둥, 목표기둥)
    # func(2, 'A', 'B', 'C')
    # func(3, 'A', 'C', 'B')
    # func(2, 'B', 'C', 'A')
    res.append([첫기둥, 목표기둥]) # 첫기둥에서 목표기둥으로 이동 : [A-B], [A-C], [B-C] 
    func(n-1, 중간기둥, 목표기둥, 첫기둥)
    # func(1, 'C', 'B', 'A') 호출 
    # func(2, 'B', 'C', 'A') 호출     
    # func(2, 'A', 'C', 'B') 호출     
func(3, 'A', 'C', 'B') 

• 함수호출 과정
  • 시작 호출 : func(3, 'A', 'C', 'B')
  • 첫번째 재귀식 호출 : func(2, 'A', 'B', 'C') ⇢ func(1, 'A', 'C', 'B') 👈 [A-C] 출력 & return(종료)
  • return 되었기 때문에 func(2, 'A', 'B', 'C')로 돌아옴
  • res.append([첫기둥, 목표기둥]) 실행 👈 [A-B] 출력
  • 두번째 재귀식 호출 : func(1, 'C', 'B', 'A') 👈 [C-B] 출력 & return(종료)
  • return 되었기 대문에 func(3, 'A', 'C', 'B')로 돌아옴
  • res.append([첫기둥, 목표기둥]) 실행 👈 [A-C] 출력(가장 아래 원판이 목표기둥(C)로 이동)
  • 두번째 재귀식 호출 : func(2, 'B', 'C', 'A')
  • 첫번째 재귀식 호출 : func(1, 'B', 'A', 'C') 👈 [B-A] 출력 & return(종료)
  • return 되었기 대문에 func(2, 'B', 'C', 'A')로 돌아옴
  • res.append([첫기둥, 목표기둥]) 실행 👈 [B-C] 출력(가운데 원판이 목표기둥(C)로 이동)
  • 두번째 재귀식 호출 : func(1, 'A', 'C', 'B') 👈 [A-C] 출력 & return(종료)

3. 핵심 아이디어 정리

1) 원판이 1개일 때는 시작기둥(A)에서 목표 기둥(C)으로 옮김

• 원판이 1개일 때는 시작기둥(A)에서 목표기둥(C)로 이동하고, 이동했기 때문에 출력
• 또한 return 함으로써 현재 단계에서 탈출시켜 재귀호출를 진행시킴

res = []
def func(n, 시작기둥, 목표기둥, 보조기둥):
    if n == 1: # 👈 원판이 1개일 때, 시작기둥에서 목표 기둥으로 이동
        res.append([시작기둥, 목표기둥])
        return None
    func(n-1, 시작기둥, 보조기둥, 목표기둥)
    res.append([시작기둥, 목표기둥])
    func(n-1, 보조기둥, 목표기둥, 시작기둥)
func(3, 'A', 'C', 'B') 

2) 원판 n-1개를 보조 기둥으로 이동

• 원판 n-1개를 보조 기둥으로 이동하기 때문에 func(n, 시작기둥, 목표기둥, 보조기둥)를 func(n-1, 시작기둥, 보조기둥, 목표기둥)로 순서를 바꿈
• 즉, 원판이 2개일 때는 원판 1개를 보조 기둥으로 옮기고, 원판이 3개일 때는 원판 2개를 보조 기둥으로 옮김

res = []
def func(n, 시작기둥, 목표기둥, 보조기둥):
    if n == 1: 
        res.append([시작기둥, 목표기둥])
        return None
    func(n-1, 시작기둥, 보조기둥, 목표기둥) # 👈 원판 n-1개를 보조 기둥으로 이동
    res.append([시작기둥, 목표기둥])
    func(n-1, 보조기둥, 목표기둥, 시작기둥)
func(3, 'A', 'C', 'B') 

3) 가장 큰 원판을 목표 기둥(C)으로 이동

• n-1개를 보조기둥(B)로 옮겼다면, 다음 단계로 가장 큰 원판을 목표 기둥(C)로 이동
• 즉, 원판이 3개일 때 원판 2개를 보조기둥(B)로 모두 옮겼다면 시작기둥(A)에 남은 원판 1개를 목표기둥(C)로 이동

res = []
def func(n, 시작기둥, 목표기둥, 보조기둥):
    if n == 1: 
        res.append([시작기둥, 목표기둥])
        return None
    func(n-1, 시작기둥, 보조기둥, 목표기둥) 
    res.append([시작기둥, 목표기둥]) # 👈 가장 큰 원판을 목표 기둥(C)으로 이동
    func(n-1, 보조기둥, 목표기둥, 시작기둥)
func(3, 'A', 'C', 'B') 

4) 보조기둥(B)와 시작기둥(A)를 swap

• 가장 큰 원판을 목표기둥(C)로 옮겼기 때문에 사실 이 원판은 이동할 일이 없어 영향을 미치지 않기 때문에 존재하지 않다고 생각해볼 수 있음
• 그럼 남은 원판으로 하노이의 탑 알고리즘을 시작하는 것과 같은 이동 횟수를 발생시킴
• 이에 보조기둥(B)에 남은 원판을 시작기둥(A)와 swap시켜 다시 시작하는 것과 마찬가지임
• 즉, 3개 원판으로 시작하였을 때, 2개의 원판을 보조기둥(B)로 이동시키고 시작기둥(A)에 남은 가장 큰 원판을 목표기둥(C)로 옮긴 것은 원판 2개로 하노이 탑을 하는 것과 같은 이동 횟수를 발생시킴

res = []
def func(n, 시작기둥, 목표기둥, 보조기둥):
    if n == 1: 
        res.append([시작기둥, 목표기둥])
        return None
    func(n-1, 시작기둥, 보조기둥, 목표기둥) 
    res.append([시작기둥, 목표기둥]) 
    func(n-1, 보조기둥, 목표기둥, 시작기둥) # 👈 보조기둥(B)와 시작기둥(A)를 swap
func(3, 'A', 'C', 'B') 

4. 재귀 호출 과정 요약

1) 원판이 3개일 때, 재귀 호출 과정 및 이동 경로 출력

• 7회 : [['A', 'C'], ['A', 'B'], ['C', 'B'], ['A', 'C'], ['B', 'A'], ['B', 'C'], ['A', 'C']]

f(n, 시작기둥, 목표기둥, 보조기둥)
res = []
def f(3, 'A', 'C', 'B'):
    def f(2, 'A', 'B', 'C'): 
        def f(1, 'A', 'C', 'B'): 
            res.append(['A', 'C']) 🔥 n == 1일 때,
            return None
        res.append(['A', 'B']) 🔥 가장 큰 원판을 목표기둥으로 이동
        def f(1, 'C', 'B', 'A'): # swap('A','B','C' → 'C','B','A')
            res.append(['C', 'B']) 🔥 n == 1일 때,
            return None
    res.append('A', 'C') 🔥 가장 큰 원판을 목표기둥으로 이동
    def f(2, 'B', 'C', 'A'): # swap('A','C','B' → 'B','C','A')
        def f(1, 'B', 'A', 'C'):
            res.append('B','A') 🔥 n == 1일 때,
            return None
        res.append('B', 'C') 🔥 가장 큰 원판을 목표기둥으로 이동
        def f(1, 'A', 'C', 'B'): # swap('B','C','A' → 'A','C','B')
            res.append('A','C') 🔥 n == 1일 때,
            return None

5. 하노의 탑 최종 코드

1) 최소 이동 경로

res = []
def hanoi(n, start, end, mid):
    if n == 1:
        res.append([start, end])
        return None
    hanoi(n-1, start, mid, end)
    res.append([start, end])
    hanoi(n-1, mid, end, start)
n = int(input())    
hanoi(n, 'A', 'C', 'B')
print(res) 

2) 최소 이동 횟수

res = 0
def hanoi(n, start, end, mid):
    global res
    if n == 1:
        res += 1
        return None
    hanoi(n-1, start, mid, end)
    res += 1
    hanoi(n-1, mid, end, start)
n = int(input())
hanoi(n, 'A', 'C', 'B') 
print(res)