하노이 탑 파이썬 - 재귀 함수를 사용해 보자

전체코드:

import sys
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 = []
hanoi(int(sys.stdin.readline()),1,2,3) 
print(len(move)) 
print("\n".join([' '.join(str(i) for i in row) for row in move]))
 

 

1. 하노이 탑의 코드를 만들기 위해서 하노이 탑의 규칙을 알아야 합니다

 

하노이 탑을 해 보면 규칙을 쉽게 찾을 수 있습니다

1. N개의 하노이 탑을 옮길 경우, 가장 왼쪽에 있는 N - 1개의 원반을 중간 부분으로 옮겨 줍니다

2. 그리고 가장 왼쪽에 있으며 마지막 한 개의 원반을 가장 오른쪽으로 옮겨줍니다

3. 마지막으로 중간에 있는 N - 1개의 원반을 가장 오른쪽으로 넘겨 줍니다

 

N이 3일 경우 

1 3
1 2
3 2
1 3
2 1
2 3
1 3

다음과 같은 방법으로 옮기면 될 것입니다

 

1 3
1 2
3 2

조금 더 자세히 설명하자면 위 부분은 '1. N개의 하노이 탑을 옮길 경우, 가장 왼쪽에 있는 N - 1개의 원반을 중간 부분으로 옮겨 줍니다'를 의미합니다

 

1 3

이 부분은 '2. 그리고 가장 왼쪽에 있으며 마지막 한 개의 원반을 가장 오른쪽으로 옮겨줍니다'를 의미합니다

 

2 1
2 3
1 3

마지막 부분은 '3. 마지막으로 중간에 있는 N - 1개의 원반을 가장 오른쪽으로 넘겨 줍니다'을 넘겨줍니다

 

 

 

---

2. 코드 설명 

import sys
def hanoi(n,a,b,c):
    if n==1:
        move.append([a,c]) // 원반을 옮기는 것을 의미합니다
    else:
        hanoi(n-1,a,c,b) // 1. N개의 하노이 탑을 옮길 경우, 가장 왼쪽에 있는 N - 1개의 원반을 중간 부분으로 옮겨 줍니다
        move.append([a,c]) // 2. 그리고 가장 왼쪽에 있으며 마지막 한 개의 원반을 가장 오른쪽으로 옮겨줍니다
        hanoi(n-1,b,a,c) // 3. 마지막으로 중간에 있는 N - 1개의 원반을 가장 오른쪽으로 넘겨 줍니다
 
move = []
hanoi(int(sys.stdin.readline()),1,2,3) // 1에서 3으로 옮기겠다는 뜻을 나타냅니다
print(len(move)) // 총 이동 수를 나타냅니다
print("\n".join([' '.join(str(i) for i in row) for row in move])) // 출력합니다
 

1 2
1 3
2 3

n == 2 라고 가정하고 코드를 해석해 봅시다 

 

1. hanoi 함수에 n이 2이니, n == 1이 아니므로 else로 넘어가 hanoi(1,1,3,2)가 호출됩니다

    1-1 hanoi(1,1,3,2)가 실행되며 n이 1이므로 move에 [1, 2]가 저장되고, hanoi(1,1,3,2) 함수가 종료됩니다

2. 그러면 hanoi(1,1,3,2)의 밑에 줄에 있는 move.append([a,c])가 실행되므로 move에 [1,3]이 저장됩니다

3. 그리고 다음 줄인 hanoi(1,2,1,3)이 실행됩니다.

    3-1 hanoi(1,2,1,3)이 실행되며 n이 1이므로 move에 [2,3]이 저장되고 hanoi(1,2,1,3) 함수가 종료됩니다 

 

그리고 move를 출력하면 [1,2] [1,3], [2,3]이 저장되어 n == 2일때 하노이 탑을 옮기는 회수가 나왔습니다

 

1 3
1 2
3 2
1 3
2 1
2 3
1 3

---

n == 3일때의 코드를 해석해 봅시다

 

1. hanoi(3,1,2,3) 함수에 n 이 3이니, n == 1이 아니므로 else로 넘어가 hanoi(2,1,3,2)가 호출됩니다

    1-1 hanoi(2,1,3,2) 함수에 n이 2이니, n == 1이 아니므로 else로 넘어가 hanoi(1,1,2,3)이 호출됩니다

        1-1-1 hanoi(1,1,2,3) 함수에  n이 1이니, n == 1이므로 move에 [1,3]이 저장되고, 함수가 종료됩니다

        1-1-2 다음 줄인 move.append([a,c])가 실행되므로 move에 [1,2]가 저장됩니다

        1-1-3 hanoi(1,3,1,2) 함수에  n이 1이니, n == 1이므로 move에 [3,2]가 저장되고, 함수가 종료됩니다

    1-2 그리고 hanoi(2,1,2,3)의 밑에 줄에 있는 move.append([a,c])가 실행되므로 move에 [1,3]이 저장됩니다

    1-3 그리고 다음 줄인 hanoi(2,2,1,3)가 실행됩니다.

        1-3-1 hanoi(1,2,3,1) 함수에  n이 1이니, n == 1이므로 move에 [2,1]이 저장되고, 함수가 종료됩니다

        1-3-2 다음 줄인 move.append([a,c])가 실행되므로 move에 [2, 3]이 저장됩니다.

        1-3-3 hanoi(1,1,2,3) 함수에  n이 1이니, n == 1이므로 move에 [1,3]이 저장되고, 함수가 종료됩니다

---

전체코드:

import sys 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 = [] hanoi(int(sys.stdin.readline()),1,2,3) print(len(move)) print("\n".join([' '.join(str(i) for i in row) for row in move]))   Colored by Color Scripter

cs