[파이썬] 단계별 백준 문제 풀기 - 11729 재귀함수 (하노이 탑 이동 순서)

문제

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

 

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

 

---

<<코드>>

#n = 원반 갯수, f = 출발지(from) , b = 경유지(by), t = 목적지(도착지) to

def hanoi(n,f,b,t):
  if n ==1 :
   print(f,t)
  else:
    hanoi(n-1,f,t,b) #원반 n-1개를 출발지 1번(f) 장대에서 2번장대인(b)로 이동
    print (f,t) #제일 큰 원반을 1(f)에서 3(t)으로 이동
    hanoi(n-1,b,f,t) #다시 원반 n-1개를 2번장대(b)에서 3번장대(t)로 가야한다.

  
n = int(input()) 

# 몇번 옮겼는지 카운트 세는 함수 만들기
#n-1개를 중간으로 옮기는 횟수 + 큰원판을 3으로 옮기는 횟수 1 + 중간에 옮겨놓은 n-1을 3번째로 옮기는 횟수
# 즉 2(n) = 2(n-1) + 1 + 2(n-1)
def count(n): #count(n) = count(n-1) + 1 + count(n-1) 
  if n > 1:
    return 2*count(n-1)+1
  else: # n=1일때는 하나의 원판이라 1번
    return 1

print(count(n)) #옮긴 횟수
hanoi(n,1,2,3)

 

<<결과값>>

$ python main.py
3

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

---

재귀함수!!! ٩(๑`^´๑)۶ 아 너무 어렵다.. 재귀함수의 다른 예제들 중에서도 하노이탑은 너무 이해하기 어려웠다.

식은 간단한데, 이걸 어떻게 이렇게 구현할 수 있지...? 고대 그리스 수학자 정도는 되어야하나보다 흑흑 (자괴)

 

하노이탑의 핵심은

N개의 원반 중, 제일 큰 원반을 제외한 (N-1)개의 원반들을 중간 기둥에 옮기고, 제일 큰 기둥을 목적지 기둥으로 옮긴 후 마지막으로 큰 원반을 목적지 기둥에 옮겨주는 것이다.

 

이를 이해하는데 도움을 준 유튜브 링크를 걸어놓아야겠다.. 

내 설명보다 유튜브를 보는것이 이해가 훨씬 빠를 것이다ㅜㅜ 나도 잊을만할 때에 다시 봐야겠다.

 

 

재귀함수란?

하노이의 탑 설명