[백준 2024/09/29] 1914번 하노이 탑

1. 문제

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

 

2. 접근 방법

 

 

만약, 3개의 하노이 탑을 옮긴다고 생각했을 떄, 2개의 탑을 우선, 중간 단계로 이동 시키고, 

마지막 base를 마지막 막대기로 이동시키고, 다시 중간 단계 2개의 탑을 마지막 단계로 이동시킨다고 생각하면 쉽다.

 

중간 막대로 2개의 탑을 옮기는 것과 마지막 막대로 2개의 탑을 옮기는 것은 같은 과정이다. 단지, 막대기 위치만 다를 뿐이다.

 

이렇게 알게 된 3개의 탑을 옮기는 방법을 이용해서, 3개의 탑을 중간 막대기로 옮기고, base를 맨 마지막 막대기로 옮기고, 중간 막대기에 있던 3개의 탑을 마지막 막대로 옮기면 된다.

 

즉, n개의 탑의 이동 공식을 이용해서 n+1개의 탑의 이동 공식을 유도할 수 있는 것이다.

 

따라서 최종 움직임은 n개의 탑을 이동 시킬 때, k 번이 필요하다고 하면, 

n+1개의 탑을 이동시키기 위해서는

k*2 (n개의 탑을 중간 막대기로 옮기고, 중간 막대기에 있던 탑을 마지막 막대기로 옮기는 과정)+ 1 (base를 첫 막대기에서 마지막 막대)이 필요하다.

 

def hanoi(fromm, togo, bypass, n):
    if n == 1:
        print(fromm, togo)
        return

    hanoi(fromm, bypass, togo, n-1)
    print(fromm, togo)
    hanoi(bypass, togo, fromm, n-1)

 

처음에 hanoi로 받은 순서 fromm, togo, bypass는 이름 그대로를 나타낸다.

fromm 은 시작막대를 의미하며, 

togo는 가고 싶은 막대

bypass는 중간에 거쳐가는 막대라고 할 수 있을 것이다.

 

n이 1 일 떄는, 한 개의 탑을 옮길 때 이므로 그 과정을 출력해 주어야 한다.

n이 2 이상일 때의 hanoi(...) 코드는 여러개의 탑을 옮기는 과정을 의미하므로 출력하는 것이 바람직하지 않다.

 

다음으로 hanoi(fromm, bypass, togo, n-1)을 확인하여 보면

처음 시작 막대에 있던 fromm에서 중간 막대로 탑을 옮기고 싶다.

따라서, togo 자리에 bypass를 옮기고 togo를 bypass로 거쳐가는 것으로 둔다.

 

따라서 이 과정은 2개의 탑을 중간 단계의 막대로 옮기는 것을 의미한다.

 

print(fromm, togo)는 첫 막대기에 있던 base를 마지막 막대기로 옮기는 것을 의미한다.

 

이제 다음 단계로 중간 막대기로 옮겼던 2개의 탑을 마지막 막대기로 옮겨줘야 한다.

bypass 에 옮겨 두었던 탑을 togo로 옮기고자 하며 그렇기에 거쳐가는 막대기는 fromm이 되게 된다.

 

3. 코드

def hanoi(fromm, togo, bypass, n):
    if n == 1:
        print(fromm, togo)
        return

    hanoi(fromm, bypass, togo, n-1)
    print(fromm, togo)
    hanoi(bypass, togo, fromm, n-1)


def get_move_num(n):
    moved = 1
    for i in range(n-1):
        moved = 2 * moved + 1
    return moved


if __name__ == "__main__":
    n = int(input())
    print(get_move_num(n))
    if n <= 20:
        hanoi(1, 3, 2, n)