[BOJ] 11729 하노이 탑 이동 순서 (Python, Recursion)

🌱 문제

11729번: 하노이 탑 이동 순서

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

 

🌱 풀이

바킹독님의 알고리즘 강의 영상의 풀이법을 참고했습니다.

우선, 아래 그림처럼 n번째 원판을 1번 장대에서 3번 장대로 옮기기 위한 과정을 생각해보겠습니다.

 

1. n-1개의 원판을 1번에서 2번 장대로 옮긴다.

 

2. n번 원판을 1번에서 3번 장대로 옮긴다.

 

3. n-1개의 원판을 2번에서 3번 장대로 옮긴다.

 

이를 귀납적으로 설명하면, 원판 n-1개를 장대 a번에서 장대 b번으로 옮길 수 있다면, 원판 n개를 장대 a'에서 장대 b'번으로 옮길 수 있다는 의미입니다. 

따라서 원판 n개를 a번 장대에서 b번 장대로 옮기는 함수를 재귀식으로 나타내면 다음과 같습니다.

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

재귀 함수의 base condition은 n이 1일 때에는 내가 원하는 곳으로 무조건 옮길 수 있으므로 장대 a에서 b로 옮기는 것을 출력하면 됩니다.

코드로 나타내면 다음과 같습니다.

def hanoi(n, a, b):
    if n == 1:
        movements.append((a, b))
        return
    hanoi(n-1, a, 6-a-b)
    movements.append((a, b))
    hanoi(n-1, 6-a-b, b)

• hanoi(n, a, b)는 원판 n개를 장대 a에서 b로 옮기는 함수입니다.
• 위에서 설명한 3개의 단계를 그대로 재귀적으로 구현하였고, base condition 또한 작성하였습니다.

 

🌱 정답 코드

# !/usr/bin/env python
# -*- coding: utf-8 -*-
# boj 11729 하노이탑

n = int(input())

count = 0
movements = []


def hanoi(n, a, b):
    if n == 1:
        movements.append((a, b))
        return
    hanoi(n-1, a, 6-a-b)
    movements.append((a, b))
    hanoi(n-1, 6-a-b, b)


hanoi(n, 1, 3)
print(len(movements))
for move in movements:
    print(*move)