백준 1914 하노이 탑 [python]

골드 5

💡아이디어

하노이탑 이동원리를 까먹어서..풀이 블로그를 참고했다

n이 원판 개수일 때, 하노이 탑의 이동횟수 공식은 2 ^ (n-1) 이다

 

a / b / c 번 기둥이 있을 때

1 > 1번 기둥에 n개의 원판이 있을때 가장 밑 원판을 제외한 n-1개의 원판을 보조기둥(b번)으로 옮긴다

2 > 가장 밑 원판을 목표기둥(c번)으로 옮긴다

3 > 보조기둥에 있는 n-1개의 원판을 목표기둥으로 옮긴다

 

이를 재귀함수로 구현하면 되는 문제였다.

 

# n == 1 일때

기둥 1에서 바로 기둥 3으로 옮기면 이동횟수는 1번이다.

 

 

# n > 1 일때

출처 : https://study-all-night.tistory.com/6

 

풀이 과정

입력 : 원판 개수

출력 : 이동 횟수 / 이동과정 (n <=20 일때)

 

1. n-1 판을 보조 탑으로 옮김

2. 1개 판만 목표 탑으로 옮김

3. n-1개의 판을 목표 탑으로 옮김

4. 1~3 과정을 반복(재귀함수)

 

코드

n = int(input())
print(2**n-1)
if(n <= 20): # 원판 개수가 20개 이하일 경우에만 출력하는 조건을 걸어준다
  f(n, 1, 2, 3)

def f(n, a, b, c):
  if(n == 1):
    print(a, c, sep = " ") # 원판이 1개일때는 a->c로 원판을 옮김 
  else:
    f(n-1, a, c, b) # step 1 : n-1개의 원판을 a-> b로 옮김
    f(1, a, b, c) # step 2 : 가장 큰 원판 1개를 a->c로 옮김
    f(n-1, b, a, c) # step 3 : step 1의 n-1개의 원판을 b->c로 옮김