[Python] BOJ 1914 : 하노이 탑

https://www.acmicpc.net/problem/1914

문제는 위 링크 참고. 

 

* 요구사항

• 한번에 한 판만 옮길 수 있다.
• 쌓아 놓은 원판은 항상 위의 것이 아래 보다 작아야 한다.
• 출력 결과 첫 줄에 옮긴 횟수 k 를 출력
• N <= 20 인 경우 수행 과정도 출력

* 설계

• 재귀함수를 이용한다. 
  • 재귀함수란, 자기 자신을 호출하는 함수를 말한다. 
    • 그렇기 때문에 base case를 지정해 놓지 않으면 무한히 반복된다. 
• def hanoi (N, start, end, mid)
  • 처음 인자를 받을 때, N(판의 개수, 시작점, 끝점(모든 판이 최종적으로 위치하게 될 지점), 중간 지점( 시작점에서 끝점으로 이동할 때, 거치는 지점. 단, base case의 경우는 바로 시작점에서 끝점으로 이동한다.)
  • base case : N == 1일 경우
    • start(시작점) 에서 end(끝점) 으로 옮긴다. 
  • 그 외의 경우
    • 가장 큰 원판을 제외하고 가운데 모아줘야함. 
      
      • 큰 원판을 옮기기 전에 작은 원판들을 다른 곳으로 옮겨서 공간을 만들어야 함. 
    • 중간에 있던 N -1 개의 원판을 목표 기둥(끝점)으로 이동하는 과정. 

* 구현

move_count = 0  # Moves tracker

def hanoi(N, start, end, mid):
    global move_count
    if N <= 20:
        if N == 1:
            move_count += 1
            print(f"Move {move_count}: {start} -> {end}")
            return
        else:
            hanoi(N-1, start, mid, end)
            move_count += 1
            print(f"Move {move_count}: {start} -> {end}")
            hanoi(N-1, mid, end, start)

hanoi(3,1,3,2)

• 위 코드는 이해를 돕기 위해 작성되었습니다. 백준에 그대로 제출 하시면 안됩니다.