[백준/Python] 11729 하노이 탑 이동 순서 (재귀)

재귀가 너무너무 어렵다.

재귀 연습을 위해 기본기에 도움을 준다는 하노이 탑 문제를 풀어보기로 했다.

---

출처 : Baekjoon Online Judge (https://www.acmicpc.net/problem/11729)

출처 : Baekjoon Online Judge (https://www.acmicpc.net/problem/11729)

---

문제의 이해를 돕기 위해, 예제로 나온 입출력 시, (N==3 일 때)

원판이 어떻게 움직이는 지 영상을 제작했다.

 

---

[ 코드 ]

 

# #17729 하노이 탑 이동 순서

# 0. 입력 값 숫자형으로 변환
# n : 입력받은 숫자
n = int(input())

# rod1, rod2, rod3 : 각 위치에 있는 장대의 번호
def hanoi(n, rod1, rod3, rod2):

    ## base case
    # 원판이 하나일 떄는 그냥 rod1 -> rod3으로 옮기면 끝난다.
    if n == 1: 
        print(rod1, rod3)
    
    ## recursion
    else:
        # 1. 원판 n-1개를 rod1에서 rod2로 옮긴다. (rod3를 보조 기둥으로)
        hanoi(n-1, rod1, rod2, rod3)

        # 2. n번째 원반 = 제일 밑에 있는 원판을 목적지(rod3)로 이동
        print(rod1, rod3)

        # 3. rod2(가운데 장대)에 있는 원반 n-1개를 목적지(rod3)로 이동 (rod1를 보조 기둥으로)
        hanoi(n-1, rod2, rod3, rod1)

# 테스트
print(n**2 -1)
hanoi(n, 1, 3, 2)

---

[ 해설 ]

 

음.. 누가 기본이라고 했지?ㅎㅎ

 

하노이 원탑의 이동 규칙은 아래와 같다.

 

n개의 원판이 있을 때, 

1. n-1개의 원판을 1번째 장대에서 2번째 장대로 옮긴다.
   (*n-1개의 원판들 : n번 원판(=맨 밑에 있는 원판)을 제외한 나머지 원판들)
2. n번 원판(=맨 밑에 있는 원판)을 1번째 장대에서 3번째 장대로 옮긴다.
3. 나머지 n-1개의 원판들을 다시 2번째 장대에서 3번째 장대로 옮긴다.

 

이 문제는 원판이 1개일 때, 2개일 때, 3개일 때, .., n개 일 때 점점 n-1일 때의 함수를 재귀로 호출해서,

문제를 해결하는 문제이다.

 

재귀 문제이기 때문에 base case(재귀가 끝나는 조건) 가 필요하다.

이 문제의 base case는 n이 1일때, 1번째 장대 -> 3번째 장대로 옮기는 값을 출력하며 끝내는 것이다.

 

n이 그 외의 값일 때는 n==1때까지 계속 n-1로 recursion한다 .

 

+

 

이동 횟수는 n²-1번이다.

 

난 아마.. 이 문제를 이해할 때까지 계속 recursion할꺼같다...