[백준 11729] 하노이 탑 이동 순서

11729번: 하노이 탑 이동 순서

알고리즘 : 재귀

난이도 : 골드Ⅴ

 

1. 문제요약

• 20이하의 자연수 n이 주어지는데, n은 하노이 탑의 높이를 의미한다.
• 1번축에 쌓여진 높이 n의 하노이 탑을 3번축으로 옮기는데 필요한 최소 횟수와 그 순서를 출력해야 한다. 예를들어 n = 3인 경우 옮기는데 필요한 횟수는 7번이고, 그 순서는 1 3(1번탑 최상단 원판을 3번탑으로 이동) -> 1 2 -> 3 2 -> 1 3 -> 2 1 -> 2 3 -> 1 3이 된다.

2. 아이디어

• 하노이탑 가장 밑 원판을 기준으로 생각해보자. 맨위의 원판부터 순서를 매길때 1,2, ... , n-1 번째 원판을 이동시킨 후에야 비로소 마지막 n번째 원판을 꺼낼 수 있다.
• n번째 원판을 꺼내는 순간은 어떤 모양일까? 2번째 축에 1부터 n-1번째 원판이 차곡차곡 쌓여있을 것이다. 이러한 모습에 이르러야 n번째 원판을 3번째 축으로 이동시킬 수 있다.
• n번째 원판을 3번축으로 옮긴 후에는 2번째 축에 쌓여 있는 원판을 3번째 축으로 옮겨주어야 하는데, 이는 높이 n-1인 하노이탑 이동문제와 동일하다.
• 정리하면, 결국 높이 n의 하노이 탑 문제는 1) 높이 n-1의 하노이탑 문제 (축1에서 축2로), 2) 마지막 원판 이동 (축1에서 축3으로), 3) 높이 n-1의 하노이탑 문제 (축2에서 축3으로) 를 합친 문제가 된다.
• 이동순서의 경우에서도 높이 n-1의 하노이탑 이동순서에 직결되는데, 1)에서는 2와 3을 바꿔주면 되고 3)에서는 1과 2를 바꿔주면 된다. 1)과 3)의 중간인 2)에서 마지막원판의 이동인 '1 3' 을 추가해주면 높이 n의 하노이탑 이동순서가 완성된다.
• 높이 n에서 이동횟수는 높이 n-1에서의 이동횟수의 두배에 1을 더한 값이 되고 높이 1인 경우 이동횟수는 1이므로 높이 n인 경우 이동횟수는 $2^n-1$이 됨을 알 수 있다. 
• 결국 이동순서를 구하는 것이 이 문제의 핵심인데, 일단 문제에서 요구한 형식은 일단 무시하고 그냥 순서대로 이어붙여 생각하기로 하자. 예를들어 높이 3인 경우 13123213212313 (1->3, 1->2 , ... 1->3 을 이어붙인 것이다) 이라는 문자열을 구하면 된다.

3. 구현과정

• 높이 x인 하노이탑의 이동순서를 구하는 함수 f(x)를 정의한다. x = 1일때는 '13'을 출력하고, 이외의 경우에는 f(x-1)로부터 위에서 생각한 방식을 그대로 적용하여 생성해낸다.
• 하노이탑 높이 n을 입력받는다. 이동횟수는 $2^n - 1$, 이동순서는 f(n)으로 구한다.
• 이동순서는 문제에서 요구하는 형식대로 한줄에 하나의 이동씩 가운데 공백을 두어 출력해야 하므로 for문을 통해 순회하면서 해당 조건에 충족하도록 구현한다.

4. 파이썬 코드

# 높이 x인 하노이탑 이동순서를 구하는 함수
def f(x):
    if x == 1:
        return '13'
    else:
        tmp1, tmp2 = '', ''
        for i in f(x - 1):
            if i == '1':
                tmp1 += '1'
                tmp2 += '2'
            elif i == '2':
                tmp1 += '3'
                tmp2 += '1'
            else:  # i == 3
                tmp1 += '2'
                tmp2 += '3'
        return tmp1 + '13' + tmp2

n = int(input())
move_num = 2 ** n - 1
move_order = f(n)
print(move_num)
for i in range(move_num):
    print(move_order[i * 2] + ' ' + move_order[i * 2 + 1])