[백준 11729번] 파이썬 - 하노이 탑 이동순서

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

11729번: 하노이 탑 이동 순서

프로그래밍을 하며 '재귀'를 접하게 되면 가장 먼저 만나게 되는 문제라고 볼 수 있다.

그만큼 유명하고 재귀를 가장 잘 표현하였다고 생각이 드는 것이 '하노이의 탑'이라고 볼 수 있다.

 

# 조건

• 세 개의 장대가 있고 첫 번째 장대에는 서로 크기가 다른 N개의 원판이 쌓여있다.
  • 한 번에 한 개의 원판만 이동 가능하며
  • 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

 

# 접근 방법

• 문제의 핵심은 '가장 큰 원반이 목표 기둥으로 옮겨진다면' 문제를 해결할 수 있다는 것이다.
• 즉, 가장 큰 원반이 옮겨지도록 나머지 원반을 보조 기둥으로 옮겨주어야 한다.
• 재귀를 통하여 시작, 보조, 목표 기둥을 상황에 맞게 바꿔주며 작성해준다.

import sys  
sys.stdin = open('input.txt')  
  
  
  
  
# 사용할 함수  
# 원판 개수, 현재위치, 도착위치  
def hanoi(N, start, end):  
    # 반드시 n-1개의 원판이 도착위치가 아닌 다른 곳으로 가야 한다.  
    # 기둥 번호의 합이 6이므로 6-현재위치-도착위치를 하면 남은 기둥의 번호를 알수 있음    # 원판이 한개 남았다면 목적지로 옮겨준다.    
    if N == 1:  
        print(start, end)  
        return  
  
    # 도착지가 아닌 보조기둥으로 옮겨주는 함수  
    hanoi(N-1, start, 6-start-end)  
    # 이동 경로 프린트 해준다.  
    print(start, end)  
    # 제일 큰 원판을 제외한 나머지를 도착 기둥으로 옮겨준다.  
    hanoi(N-1, 6-start-end, end)  
  
# 원판 개수 입력  
N = int(input())  
# 하노이의 탑 최소 이동 횟수
print(2**N-1)  
# 제곱 구해주는 함수  
# print(pow(2,N)-1)  
hanoi(N, 1, 3)

• '재귀'는 프로그래밍을 시작하는 사람들에게 '통곡의 벽'이라고 불린다고 들었다.
• 나도 아직 로직을 완벽하게 알 수 없어 구현하는 것이 힘들지만, 문제 해결 과정을 잘 그릴 수만 있다면 확연히 코드를 짧게 구성하여 보기 편하다는 장점이 있다.
• 하지만 무조건 좋은 것은 아니므로 상황에 맞게 사용하자!!

 

[참고 영상]

https://www.youtube.com/watch?v=FYCGV6F1NuY