[Python][알고리즘] 하노이의 탑

📌 하노이의 탑

📋 하노이의 탑 이란?

퍼즐 게임의 일종으로 세 개의 기둥을 이용해서 원판을 다른 기둥으로 옮기면 되고 제약 조건은 다음과 같다.

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

# 하노이 파헤치기
# 하노이의 탑 이란?
# 퍼즐 게임의 일종으로 세 개의 기둥을 이용해서 원판을 다른 기둥으로 옮기면 되고 제약 조건은 다음과 같다.
# 한 번에 한개의 원판만 옮길 수 있다.
# 큰 원판이 작은 원판 위에 있어서는 안 된다.


def hanoiTower(discNum, fromPole, toPole, otherPole):  # 시작, 목적지, 경유지
    if discNum == 1:
        print(f'시작 : {fromPole} 에서 목적지 : {toPole}로 옮긴다')
        return

    hanoiTower(discNum - 1, fromPole, otherPole, toPole)  # 시작, 목적지, 경유지
    print(f'시작 : {fromPole} 에서 목적지 : {toPole}로 옮긴다')
    hanoiTower(discNum - 1, otherPole, toPole, fromPole)


hanoiTower(3, 1, 3, 2)

시작 : 1 에서 목적지 : 3로 옮긴다
시작 : 1 에서 목적지 : 2로 옮긴다
시작 : 3 에서 목적지 : 2로 옮긴다
시작 : 1 에서 목적지 : 3로 옮긴다
시작 : 2 에서 목적지 : 1로 옮긴다
시작 : 2 에서 목적지 : 3로 옮긴다
시작 : 1 에서 목적지 : 3로 옮긴다

참고 : 재귀함수가 뭔가요? (Feat. 하노이의 탑)