백준 알고리즘 11729 [파이썬]

 

배운 내용

재귀함수관련 문제중에 제일 유명하다고 할 수 있는 하노이 탑 이동 순서 문제를 풀어보았는데, 재귀함수 알고리즘 문제를 풀어본적 없는 나에겐 너무 어려운 문제였던것 같다. 하지만 이 문제를 풀고 이해하면서 재귀함수에대해서 잘 이해할 수 있었다. 

 

문제 풀이 설명은 코드안에 해놨습니다.

 

 

문제 

 

 

문제풀이

 

# 재귀함수
# 조건에 맞으면 function을 계속 반복시킨다.
n = int(input())
def hanoi_recursive(n, a, b, c):
  if n == 1:
    print(a, c)
    return

  else:
    hanoi_recursive(n-1, a, c, b) # 제일 밑에 있는 원판을 제외한 다른 원판들을 보조지역에 옮긴다.
    print(a, c) # 제일 밑에있는 원판을 목표지점에 옮긴다.
    hanoi_recursive(n-1, b, a, c) # 보조지역에 있던 다른 원판들을 목표지점으로 옮긴다.
    
    
sum = 1 # 위에 함수에 print()가 몇번 적용되는냐가 sum 값이된다.
for i in range(n-1):
  sum = sum*2 + 1  # sum*2를 하는 이유는 함수 else안에 같은 함수가 2개있고, +1 하는 이유는 함수 else안에 print가 하나 있기 때문입니다. 
print(sum)
# (원판의 개수, 시작지점, 보조, 목표지점)
hanoi_recursive(n, 1, 2, 3)