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

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

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

11729번: 하노이 탑 이동 순서

오랜만에 하노이탑 문제를 푼 것 같다. 분할 정복 문제의 대표적인 문제 중 하나인 하노이 탑이다.

 

추가: 맨 아래에는 또 오랜만에 풀어서 추가한 하노이탑 문제의 코드다.

 

보통 3지점을 모두 인수로 넘기면서 (start, to, by)로 넘기면 출력 전후에 hanoi(start, by, to)와 hanoi(by, to, start)로 각각 호출하게 된다.

근데 처음에 기억 안나고 그 부분을 그냥 리스트로 start와 to를 지워서 남는 곳으로 보내주었다... 

 

여기서 이동 횟수가 2**k - 1이 된 이유는 계산을 해보면 된다.

 

예제 입력처럼 3의 높이가 주어졌다고 하면 높이가 3인 탑을 (1)->(3)으로 보내야 한다. 그러면 높이가 2인 탑을 (1)->(2)로 우선 보내야하며, 마찬가지로 높이가 2인 탑을 (1)->(2)로 보내기 위해서는 높이가 1인 탑을 (1)->(3)으로 보내주어야 한다.

 

그럼 계산이 되는 순서대로 높이가 1인 탑을 (1)->(3)으로 보내주기 위해서 1번의 이동만 있으면 된다.

그 상태에서 높이가 2인 탑을 (1)->(2)로 보내주기 위해서는 다음과 같이 된다.

<기존>
 2 
 3       1
(1) (2) (3)

-->
 
 3   2  1
(1) (2) (3)

-->
     1
 3   2  
(1) (2) (3)

 

즉 1을 1->3으로 보내준 이후 2번의 추가 움직임이 필요하다. 따라서 총 움직인 횟수는 1+2가 된다.

마찬가지로 계속 계산을 해보면 높이가 2인 탑을 (2)에 쌓은 이후 높이가 3인 탑을 (3)을 지으려 하면 움직이는 횟수는 4회가 된다. 총 움직인 횟수는 1+2+4가 된다.

 

계속 계속하다 보면 공비가 2인 등비수열의 합을 계산하게 된다.

 

def hanoi(level, start, to):
    if level < 1: return
    global cnt, move
    go = [1, 2, 3]
    go.remove(start)
    go.remove(to)

    hanoi(level-1, start, go[0])
    print(start, to)
    hanoi(level-1, go[0], to)

k = int(input())
print(2**k-1)
hanoi(k, 1, 3)

 

새롭게 풀어본 코드다.

def hanoi(t, start, dest, remain):
    if t == 0: return
    hanoi(t-1, start, remain, dest)
    print(start, dest)
    hanoi(t-1, remain, dest, start)
n = int(input())
print(2**n-1)
hanoi(n, 1, 3, 2)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다