백준 알고리즘(파이썬) - 11729번

하노이 탑 이동 순서

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

11729번: 하노이 탑 이동 순서

 

하노이탑의 원리는 알겠는데 수행 과정을 출력하는 방법을 생각해봐도 떠오르지 않았다. 함수에 변수를 하나만 넣을 생각을 해서 탑을 옮기는데 어떨 땐 첫 번째 막대에서, 어떨 땐 두 번째 막대에서 이동해야 하는 것을 어떻게 다뤄야 할지 몰랐다.

결국 검색을 통해 답을 알아봤다.

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)

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

 

하노이 탑 이동 과정을 단순하게 표현하면 다음과 같다.

1) n-1개의 탑을 start, end가 아닌 다른 막대에 이동시킨다.

2) 마지막 한 개를 end로 이동시킨다

3) n-1개의 탑을 end로 이동시킨다

 

여기에서 나는 start, end, 나머지 하나를 어떻게 표현할지 고민하다가 답을 찾지 못했다. 다른 풀이를 보니 다음과 같이 표현했다.

hanoi(n-1, start, 6-start-end)

1, 2, 3번 막대가 있으므로 모두 더한 6에서 start, end를 빼면 옮길 막대를 구할 수 있다.

 

나는 1->3 이동할땐 이런조합, 2->3 이동할땐 저런 조합으로 따로 코드를 작성해서 알려줘야 된다고 생각했는데 막상 답을 찾아보니 간단해서 놀랐다. print만 사용한 재귀함수에서 저런 형식이 가능하다니 신기했다.

 

이동 횟수는 (n개블럭이동) = 2*(n-1개블럭이동) + 1 이니까2**n + 1로 표현할 수 있다.(나무위키 참고함)

 

참고한 페이지https://study-all-night.tistory.com/6

[백준 11729번] 하노이 탑 이동순서 - Python(파이썬) 자세한 풀이

알고리즘, 이동횟수https://namu.wiki/w/%ED%95%98%EB%85%B8%EC%9D%B4%EC%9D%98%20%ED%83%91

조금 코드가 다르지만 재귀함수 실행 순서가 나와있음

https://data-jj.tistory.com/34

백준 11729번 : 통곡의 하노이 탑 (feat. python)