[백준-python] 11729번 : 하노이 탑 이동 순서(hanoi top in python)

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

11729번: 하노이 탑 이동 순서

---

코드

# hanoi function def
def hanoi(n,a,b,c):
    if n==1:
        move.append([a,c])
    else:
        hanoi(n-1,a,c,b)
        move.append([a,c])
        hanoi(n-1,b,a,c)

move = [] # 이동 경로를 담을 list
hanoi(int(input()),1,2,3) # function 실행

print(len(move)) # 이동 횟수
print("\n".join([' '.join(str(i) for i in row) for row in move])) # 이동 경로 출력

---

코드설명

원판이 4일때를 예로들어 설명한다.

그림1

네 개의 원판을 1에서 3으로 모두 옮기기 위해서는 

먼저, 1,2,3번 세 개의 원판이 모두 2에 있어야 한다. (그래야 4번째 원판을 3으로 옮길 수 있기 때문)

그림2

그 전에, 세 개의 원판을 모두 2로 옮기기 위해서는 1,2번 두 개의 원판이 모두 3에 있어야 한다.

그림3

그 전에, 두 개의 원판 역시 마찬가지이다.

그림4

즉, 재귀를 이용해야 한다.

단, 순서는 n이 짝수일 때는 1번원판을 2번원판으로 먼저 이동,

홀수일 때는 1번원판을 3번원판으로 먼저 이동한다.

 

이때, 두 개의 원판을 한 곳으로 옮기는 그림4의 상황에서

2번 원판을 3에 옮기기 위해 1번 원판이 2에 있어야 하고,  ..... ①

2번 원판을 3으로 옮긴 후 ....................................................................... ②

다시 1번을 3으로 옮겨야 한다. ............................................................. ③

 

pseudocode로는 다음과 같다.

function f :

    f(1번 원판, 1->2) ... ①

    2번원판 1->3 ........ ②

    f(1번 원판, 2->3) ... ③

이 pseudocode를 일반화하면 위의 코드가 된다.

---

코드예시

 

ex) n=3

7
1 3
1 2
3 2
1 3
2 1
2 3
1 3

 

ex) n=4

15
1 2
1 3
2 3
1 2
3 1
3 2
1 2
1 3
2 3
2 1
3 1
2 3
1 2
1 3
2 3

 

ex) n=5

31
1 3
1 2
3 2
1 3
2 1
2 3
1 3
1 2
3 2
3 1
2 1
3 2
1 3
1 2
3 2
1 3
2 1
2 3
1 3
2 1
3 2
3 1
2 1
2 3
1 3
1 2
3 2
1 3
2 1
2 3
1 3