70 - (파이썬) 하노이탑

# 하노이의 탑

: 하노이의 탑(Tower of Hanoi)은 퍼즐의 일종이다. 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다.

게임의 목적은 다음 세 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것이다.

1. 한 번에 한개의 원판만 옮길 수 있다.
2. 가장 위에 있는 원판만 이동할 수 있다.
3. 큰 원판이 작은 원판 위에 있어서는 안 된다.

# 유래

"인도 베나레스에 있는 한 사원에는 세상의 중심을 나타내는 큰 돔이 있고 그 안에 세 개의 다이아몬드 바늘이 동판 위에 세워져 있습니다. 바늘의 높이는 1 큐빗이고 굵기는 벌의 몸통만 합니다. 바늘 가운데 하나에는 신이 64개의 순금 원판을 끼워 놓았습니다. 가장 큰 원판이 바닥에 놓여 있고, 나머지 원판들이 점점 작아지며 꼭대기까지 쌓아 있습니다. 이것은 신성한 브라흐마의 탑입니다. 브라흐마의 지시에 따라 승려들은 모든 원판을 다른 바늘로 옮기기 위해 밤낮 없이 차례로 제단에 올라 규칙에 따라 원판을 하나씩 옮깁니다. 이 일이 끝날 때, 탑은 무너지고 세상은 종말을 맞이하게 됩니다."

 

# 이동 횟수 구하기

: 사실 이동 횟수를 구하는 건 수열로 때려넣는 것이 프로그램 계산 속도가 훨씬 빠르다는 것을 알 수 있다. 따라서 일반적으로 원판이 n개 일 때, 2n -1번의 이동으로 원판을 모두 옮길 수 있다는 것을 알면...

원판의 개수 : 20 이동횟수 : 1048575회

 

위와 같이 출력되는 프로그램은 기존의 배운 내용으로 다음과 같이 작성하는게 장땡이다.

#이동횟수
howmany = int(input("원판의 개수: "))
print(f"이동횟수: {2**howmany - 1}회")
>>>
원판의 개수: 20
이동횟수: 1048575회

 

# 움직이는 방법

: 처음 원판이 있는 "시작 기둥"을 A, 옮겨야하는 "대상 기둥"을 B, 보조적으로 사용하는 "보조 기둥"을 "C"라고 하고 아래의 알고리즘에 따라 구현해보면

 

def 하노이탑(원판개수, 시작, 대상, 보조) :
  if 원판개수 == 1:
    print(시작, "->", 대상)

  else :
    하노이탑(원판개수 - 1, 시작, 보조, 대상)
    print(시작, "->", 대상)
    하노이탑(원판개수 - 1, 보조, 대상, 시작)

원판개수 = int(input("원판의 개수: "))
하노이탑(원판개수, "A", "B", "C")

 

계산해보면...

#이동횟수
howmany = int(input("원판의 개수: "))
print(f"이동횟수: {2**howmany - 1}회")

print()

# 움직이는 방법
def 하노이탑(원판개수, 시작, 대상, 보조) :
  if 원판개수 == 1:
    print(시작, "->", 대상)

  else :
    하노이탑(원판개수 - 1, 시작, 보조, 대상)
    print(시작, "->", 대상)
    하노이탑(원판개수 - 1, 보조, 대상, 시작)

원판개수 = int(input("원판의 개수: "))
하노이탑(원판개수, "A", "B", "C") 

>>>
원판의 개수: 3
이동횟수: 7회

원판의 개수: 3
A -> B
A -> C
B -> C
A -> B
C -> A
C -> B
A -> B

원판의 개수: 4
이동횟수: 7회

원판의 개수: 4
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C
A -> B
C -> B
C -> A
B -> A
C -> B
A -> C
A -> B
C -> B

# 위 알고리즘을 이용해서 이동횟수를 출력해보면

counter = 0
def 하노이탑(원판개수, 시작, 대상, 보조) :
  global counter
  if 원판개수 == 1:
    #print(시작, "->", 대상)
    counter += 1
  else :
    하노이탑(원판개수 - 1, 시작, 보조, 대상)
    #print(시작, "->", 대상)
    counter += 1
    하노이탑(원판개수 - 1, 보조, 대상, 시작)

원판개수 = int(input("원판의 개수: "))
하노이탑(원판개수, "A", "B", "C") 

print(counter)
>>>
원판의 개수: 3
7

 

 

참고로) 규칙을 구하는 건 5번 정도 해봐서 유추하면 되기는 함.

이렇게

---

https://replit.com/@wh3308/hanoitab