1914. 하노이 탑

https://www.acmicpc.net/problem/1914

 

✔ 유형 : 재귀

✔ 문제 풀이: 규칙을 찾아 문제 크기를 줄여 일반화

하노이 탑 규칙

하노이 탑 규칙

 

최소한의 움직임으로 모든 원판을 크기 순서대로 1번 링에서 3번 링으로 옮겨야 한다.

밑에 있는 원판은 위에 있는 원판보다 크기가 커야한다.

 

간단한 시뮬레이션

간단한 시뮬레이션

생각을 바꿔서 마지막으로 남은 N번째 원판을 옮기려면 어떻게 해야할까?

 

하노이 탑 이동순서

하노이 탑 이동순서

 

1️⃣ n - 1 개의 원판을 기둥 1에서 2로 옮긴다.

2️⃣ n번 원판을 기둥 1에서 기둥 3으로 옮긴다.

3️⃣ n - 1개의 원판을 기둥 2에서 기둥 3으로 옮긴다.

💡 원판이 n-1 개일때 옮길 수 있으면 n개일 때도 옮길 수 있다!!

 

구현

구현

 

1. 함수의 정의

void func(a : int, b : int, n : int):
 # 원판 n개를 a번 기둥에서 b번 기둥으로 옮기는 방법을 출력하는 함수.

 

2. base condition

 n = 1 일 때 print( a, b )

 

3. 재귀식

# n-1개의 원판을 기둥 a에서 기둥 6-1-b로 옮긴다.
func(n-1, a, 6-a-b)

# n번 원판을 기둥 a에서 기둥 b로 옮긴다.
func(n, a, b)

# n-1개의 원판을 기둥 6-a-b에서 기둥 b로 옮긴다.
func(n-1, 6-a-b, b)

 

 

⬇️ 코드

n = int(input())

def hanoi( n : int, a : int, b: int):
    if( n > 20 ) : return
    if( n == 1 ) :
        print(a,b)
    
        return 

    hanoi(n - 1, a, 6-a-b)

    print(a,b)

    hanoi(n - 1, 6-a-b,b)

    
print(2**n - 1)
hanoi(n, 1, 3)