백준 11729 하노이 탑 이동 순서 파이썬 풀이

[Python] 백준 알고리즘 온라인 저지 11729번 하노이 탑 이동 순서

11729 하노이 탑 이동 순서

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

11729번: 하노이 탑 이동 순서

재귀 함수를 이용하는 문제로 머릿속에서는 쉬운 문제이지만 코드로 짜려니 어려움을 느껴 다른 분들의 블로그를 참조했다.

---

• 코드

n = int(input())
def top(n, a, b, c):
    if n == 1:
        print(a, c)
    else:
        top(n-1, a, c, b) 
        print(a, c)
        top(n-1, b, a, c)
sum = 2 ** n - 1
print(sum)

top(n, 1, 2, 3)

---

하노이 탑 알고리즘

하노이 탑

위의 그림과 같이 A, B, C를 출발, 보조, 목표라고 생각하면 맨 밑의 판을 제외하고 나머지 판들이 모두 보조(B)로 옮긴 후 마지막 판을 목표(C)에 옮기고 B의 판들을 C로 이동시키는 방법이다.

여기에서 순서는 n이 짝수일 때 맨 위의 판을 B로 이동시키고, 홀수 일 때는 맨 위 판을 C로 이동시킨다.

---

풀이 

우선적으로 최소한의 이동 값은 n = 1일 때 1, n = 2일 때 3, n = 3일 때 7, n=4일 때 15 이므로 (2^n - 1)의 식이 완성된다. 

그 후 재귀 함수로 들어가는데 2개의 판을 가진 하노이 탑을 가지고 예를 들면

• 첫 번째 판을 B로 이동 (1 2)
• 두 번째 판을 C로 이동 (1 3)
• 첫 번째 판을 C로 이동 (2 3)

최소한의 움직임 3번으로 이후 top(2, 1, 2, 3)의 함수를 실행하고 a, b, c의 순서를 바꿔가며 위의 괄호와 같이 출력하게 된다. 

if문을 활용해 재귀 함수를 종료하는 조건임과 동시에 n=1일 때는 1-3 하나의 출력 값이 나올 수 있게 A-C를 작성한다.그 후 n>1일 때 즉 else일 때는 n=2일 때를 이용해 1-2, A-B로 가는 코드, 미들이였던 B를 목표 C로 바꿔준다 그리고 n-1을 하며 재귀 함수를 이용한다. 이후 마지막 판 n=2일 때는 두 번째 판을 C로 보내는 출력을 한다, 마지막으로 두 번째에 있던 첫 번째 판을 C로 보내주는 재귀 함수를 작성하면 끝이다.크게 나눠 설명하자면 n > 1 일 때(else문) n - 1개의 판들을 B로 이동하는 재귀 -> top(n-1, a, c, b)제일 큰 판을 C로 옮기는 1-3 -> print(a, c)n-1판을 B-C로 옮기는 재귀-> top(n-1, b, a, c)로 설명된다.

여기에서 헷갈릴 수 있는 내용은 else문으로 들어가고  top1 -> print -> top 2 순으로 n==1의 조건을 완성할 때까지 실행되게 되고 top2에서는 top1을 다시 실행하며 출력하게 된다.

재귀 함수를 풀 때마다 느끼는 일이지만 코드를 보면 간단하게 보이다가도 직접 조건을 만들다 보면 머리가 뒤죽박죽이 된다. 조금 더 공부하며 스스로 정리해야 할 필요성을 느꼈다.

---

풀이 결과