Python - 알고리즘 (하노이 탑)

하노이 탑

하노이라길래 베트남인줄 알았는데 고대 인도 베나레스에 있는 한 사원 이야기란다.
64개의 원반을 처음 놓여 있던 막대에서 다른 막대로 모두 옮기면 탑은 무너지고 세상의 종말이 온다고 한다.
세상을 종말 시켜보자.

하노이 탑의 규칙은 아래와 같다.

1. 한 번에 하나의 원판만 이동할 수 있습니다.
2. 원판은 탑의 맨 위에서만 이동할 수 있습니다.
3. 작은 원판 위에 큰 원판이 올라갈 수 없습니다.

이를 풀기위한 기본 아이디어는 재귀적 접근 방식
즉 큰 문제를 더 작은 문제로 나누어 해결
뭔말이냐?
-> n-1개의 원핀을 사용해 문제를 해결한 다음 가장 큰 원판을 도착지점으로 이동
그리고 다시 n-1개의 원판을 가장 큰 원판 위로 이동시키는 과정을 반복하는 것

하노이의 탑을 풀기 위해서 우선 재귀함수에 대해서 알아야함
재귀함수란 함수에서 자기 자신을 다시 호출해 작업을 수행하는 방식임

재귀함수란?

---

나 자신을 다시 호출하는 것

• 잘쓰면 코드를 효율적으로 관리할 수 있다.

별찍기

def recusion(num):
​​​​if num > 0:
​​​​​​​​print('*' * num)
​​​​​​​​return recusion(num -1)

​​​​else:
​​​​​​​​return 1

recusion(10)

10! 구하기

def factorial(num):
​​​​if num > 0:
​​​​​​​​return num * factorial(num-1)
​​​​else:
​​​​​​​​return 1

print(f'factorial(10) : {factorial(10)}')

---

이제 문제를 풀어보자

​​​​​​​​​​​​# 원판 개수, 출발 기둥, 도착 기둥, 경유 기둥
def moveDisc(discCnt, fromBar, toBar, viaBar):
​​​​if discCnt == 1:
​​​​​​​​print(f'{discCnt}disc를 {fromBar}에서 {toBar}으로 이동!')

​​​​else:
​​​​​​​​# (disCnt-1) 개들을 경유 기둥으로 이동
​​​​​​​​moveDisc(discCnt-1,fromBar, viaBar, toBar)

​​​​​​​​#disCnt를 목적 기둥으로 이동
​​​​​​​​print(f'{discCnt} disc를 {fromBar}에서 {toBar}으로 이동!')

​​​​​​​​# {disCnt-1}개들을 도착 기둥으로 이동
​​​​​​​​moveDisc(discCnt-1,viaBar,toBar, fromBar)

moveDisc(3 ,1 ,3 ,2) #3개의 원판을 1번 기둥에서 시작해서 3번기둥까지 옮기는데 경유기동은 2번이다.

코드를 실행하면 moveDisc(discCnt-1,fromBar, viaBar, toBar)를 실행했을때

(3, 1, 3, 2) -> 2, 1, 2, 3

(2, 1, 2, 3) -> 1, 1, 3, 2

(1, 1, 3, 2) ->             #  1-1 = 0이니까  if discCnt == 1:만남

이렇게 되고

if discCnt == 1:만나니까 쭉 실행하면
print(f'{discCnt}disc를 {fromBar}에서 {toBar}으로 이동!')을 먼저 만나고
다음 print(f'{discCnt} disc를 {fromBar}에서 {toBar}으로 이동!')을 만남

(3, 1, 3, 2) -> 2, 1, 2, 3  -> 3disc를 1에서 3으로 이동 (4)

(2, 1, 2, 3) -> 1, 1, 3, 2 -> 2disc를 1에서 2로 이동 (2)

(1, 1, 3, 2) ->  1disc를 1에서 3으로 이동 (1)

(2, 1, 2, 3) -> 1, 3, 2, 1

(1, 3, 2, 1) ->  1disc를 3에서 2로 이동 (3)

(3, 1, 3, 2)

실행순서