백준 알고리즘 11729번 문제 하노이 탑

하노이 탑은 정말 유명한 대표적인 재귀 알고리즘 문제이다. 그렇기 때문이기도 하고 전에 배웠지만 또 까먹어서 정확히 개념을 정리하고자 한다.

백준 하노이 탑 문제 이미지

하노이 탑에서는 결국은 목적이 모든 원반을 하나씩 옮겨서 1에서 3으로 다 옮겨야한다. 그렇다면 이를 반복적인 부분을 고려해서 크게 3가지로 세분화 할 수 있는데,

1. 작은 원반 n-1개를 즉, 맨 아래 원반을 제외한 나머지 원반. 을 A 에서 B로 이동

2. 큰 원반인 제일 아래 원반 1개를 A에서 C로 이동

3. 작은 원반 n-1개를 다시 B에서 C로 이동

이렇게 크게 나눌 수 있다.

재귀니까 종료조건도 생각해야하는데 n-1부분 재귀를 하다보면 1개가 남을 것이다. 그 때가 종료 조건이 된다.

파이썬 코드로 옮겨 보자면

n = int(input())
a = []
def Hanoi(From,by,to,n):
    if n == 1:
        a.append(str(From)+' '+str(to))
    else:    
        Hanoi(From,to,by,n-1)
        a.append(str(From)+' '+str(to))
        Hanoi(by,From,to,n-1)

Hanoi(1,2,3,n)
print(len(a))
for i in a:
    print(i)

이렇게 된다. 백준 문제에서는 먼저 과정이 몇 줄 print가 되는지 출력을 하고 과정을 출력해야해서, 나는 배열을 이용해서 그 과정을 추가하는 방식으로 구현했다. 입출력 부분은 잘 숙지하고 문제를 풀자! 처음에 잘 보지 않고 문제를 풀어서 바로 틀려버렸다. :(

참고: 윤성우 열혈 자료구조