[Python] ⭐️백준 알고리즘 11729번 : 하노이 탑 이동 순서

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

11729번: 하노이 탑 이동 순서

 

 

 

👩‍💻문제 이해

재귀함수 알고리즘을 이용해 하노이 탑 이동순서를 출력하고 이동 횟수를 구하는 문제이다.

재귀함수는 어떤 패턴이 반복되는지 찾아내는 게 중요하다

 

출처 : https://study-all-night.tistory.com/6

 

1번지점에서 3번지점으로 탑을 옮기기 위해선 위 그림과 같은 3개의 단계가 반복된다.

 

1단계 : n-1개의 원판을 1 -> 2 이동

2단계 :  남은 한 개의 원판을 1 -> 3 이동

3단계 : n-1개의 원판을 2 -> 3 이동

 

왜 항상 혼자 생각하면 생각이 안나는지 모르겠다,,ㅠ

 

👩‍💻재귀함수를 사용한 코드 : 성공🌈

def hanoi(n, start, end) :
    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)
hanoi(n, 1, 3)

 

 

# 이동과정을 출력해야하기 때문에 
# hanoi함수는 정수 n, 시작 위치 start(1), 마지막 위치 end(3)을 변수로 가진다.

def hanoi(n, start, end) :
    if n == 1 :
        print(start, end)
        return
        # return을 쓰지 않으면 런타임에러
        # return start, end으로 쓰면 출력형태가 달라져서 print로 출력하고 return
    
    # 1단계 
    # n-1개의 원판을 1->2 이동
    # 처음 위치, 끝 위치만 변수로 받기 때문에 나머지 하나의 위치는 (1+2+3) - start - end로 둔다.
    hanoi(n-1, start, 6-start-end)
    
    # 2단계
    # 남은 하나의 원판을 1->3 이동
    print(start, end)
    
    # 3단계
    # n-1개의 원판을 2->3 이동
    hanoi(n-1, 6-start-end, end) 
    
n = int(input())
print(2**n-1)
# 하노이 탑 최소 이동횟수 = (2^n - 1)번
hanoi(n, 1, 3)