[Python/코테] 백준 11729 하노이 탑 이동 순서

11729 하노이 탑 이동 순서

문제 및 조건 설명: https://www.acmicpc.net/problem/11729

알고리즘 설계

💡idea.

어떠한 규칙은 있지만, 모든 경우를 따져주기에는 복잡해 보인다.

→ 절차지향적 사고가 아닌, 귀납적 사고로 접근하자❗ 단계별로 생각해서 일반항을 유추해 내는 것이 아니라, 특정 규칙(해당 문제에서는 'i에서 k로 이동한다.')이 반복되면 n항에도 적용이 된다는 귀납적 사고를 적용하는 것. 단계별로 어떤 모양이 될지를 고민하지 말 것. 그냥, 냅다, 적용하기.

 

즉, 가장 큰 n번 원판을 옮기기 위해서는

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

→ 재귀를 활용한다.

 

🎲step.

1. 함수의 정의 - 어떤 역할? 어떤 인자?

def func(n)	# 원판 n개를 기둥 1에서 기둥 3으로 옮기는 방법을 출력하는 함수

그러나, 이 함수는 n-1 원판을 기둥2로 옮길 때 사용할 수 없다. (기둥 3으로 옮기는 동작을 하기 때문)

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

2. base condition (종료 조건)

n=1일 때, a에서 b로 옮기도록 한다. (수행 과정을 출력해야 하므로, print한다.)

print(a, ' ', b)

3. 재귀식

a에서 b기둥으로 원판 n개를 옮기고 싶을 때

1. n-1개의 원판을 기둥 a에서 기둥 6-a-b로 옮긴다.
2. n번 원판을 기둥 a에서 기둥 b로 옮긴다.
3. n-1개의 원판을 기둥 6-a-b에서 기둥 b로 옮긴다.

func(a, 6-a-b, n-1)
print(a, ' ', b)
func(6-a-b, b, n-1)

알고리즘 구현

n = int(input())


def move(a, b, n):  # 원판 n개를 a에서 b기둥으로 옮기는 함수
    if n == 1:
        print(a, b)
    else:
        move(a, 6-a-b, n-1)
        print(a, b)  # move(a,b,1)
        move(6-a-b, b, n-1)


print(pow(2, n)-1)
move(1, 3, n)

 

이동 횟수 계산하는 방법은 이해가 잘 안되어 추후 추가하도록 하겠음 ..

---

출처:

https://youtu.be/8vDDJm5EewM?si=K0RQM7zhcAJ_-2ev&t=1154