74. 11729(하노이 탑 이동 순서)

N = int(input())


def Hanoi(A, B, C, N):  # A:1 B:2 C:3

    if N == 1:
        print("{0} {1}".format(A, C)) # 처음 print라고 정의함
        return
    Hanoi(A, C, B, N-1)
    print("{0} {1}".format(A, C)) # 마지막 print 라고 정의함
    Hanoi(B, A, C, N-1)


print((2**N)-1)
Hanoi(1, 2, 3, N)

먼저 이동 순서를 한번 보자.

하노이탑 n = 3 일때 위와 같이 이동한다.

어떻게 이동 되는지 이해가 됐는가?

그럼 설명에 들어간다.

 

재귀 함수를 사용하여 하노이탑 문제를 풀어야한다.

기본적으로 총 움직이는 횟수는 2의 들어온 값의 제곱 - 1 이다.  => (( 2**n )-1)

 

그러면 재귀함수가 실행되면서 ABC가 어떻게 되는지 쓰면

 

(1) 처음 1 2 3 => 1 3
(2) 마지막 1 3 2 => 1 2
(3) 처음 3 1 2 => 3 2
(4) 마지막 1 2 3 => 1 3
(5) 처음 2 3 1 => 2 1
(6) 마지막 2 1 3 => 2 3
(7) 처음 1 2 3 => 1 3

 

이렇게 돌아간다.

 

이건 누가 옆에서 얘기해준다고 해도 직접 어떻게 돌아가는지 머리로 생각을 해봐야 이해가 가능하다.