[파이썬 자료구조] 하노이탑

하노이탑에 대한 Python 코드입니다.

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

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

1. 한 번에 하나의 원판만 옮길 수 있다.
2. 큰 원판이 작은 원판 위에 있어서는 안 된다.

왼쪽 부터 peg1,peg2,peg3라고 할게요

peg1에 있는 디스크를 peg3에 모두 옮기려면 어떻게 해야할까요??

1. peg3에 6번 디스크가 가기위해서는 peg2에 1~5번 디스크가 있어야합니다.

2. 마찬가지로 peg2에 5번 디스크가 있기 위해서는 peg3에 1~4번 디스크가 있어야합니다.

3. peg3에 4번 디스크가 있기위해서는 peg2에 1~3번 디스크가 있어야겟죠?

4. peg2에 3번 디스크가 있기위해서는 peg3에 1~2번 디스크가 있어야합니다.

 

def tower_of_hanoi(nDisks, peg1, peg2, peg3): 
    if nDisks: # 디스크가 비어있으면 종료합니다.
        tower_of_hanoi(nDisks-1, peg1, peg3, peg2) #n-1개의 디스크를 peg1에서
        move_single_disk(peg1, peg3) 
        tower_of_hanoi(nDisks-1, peg2, peg1, peg3)
 
def move_single_disk(src, dst): #디스크를 움직이는 함수
    x = src.pop(0)
    dst.insert(0,x)
    print("move a single disk from sPeg to dPeg. {}, {}, {}".format(sPeg, aPeg, dPeg))
 
tower_of_hanoi(len(sPeg), sPeg, aPeg, dPeg)