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

하노이 탑 이동 순서

분류

• 재귀

문제 설명

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

문제풀이

혼자서 끙끙 고민하다가 유튜브 알고리즘 영상을 통해 이해에 도움을 받고 풀었다.
재귀 문제는 왜 이렇게 사고하기 힘들까..ㅠ 머리에 쥐가 난다.
계속 풀다보면 언젠가는 깨우침이 있겠지란 마음을 갖는 게 최선인 것 같다.

하노이 탑은 3개의 기둥에서 시작 기둥에 쌓은 탑들을 목표로 하는 곳에다가 똑같이 쌓는 것이 목적인데
그러기 위해서는 도착, 보조, 목표 기둥 이 3가지를 재귀에서 활용하여야 한다.

1. 기둥이 1개만 있으면 바로 목표 기둥으로 보낸다.

a = 시작기둥, b = 목표기둥
if n == 1:
	print(a, b)

2. 기둥이 1개 이상이면 보조 기둥으로 먼저 보낸다.
3. 이후에 보조기둥에서 목표지점으로 보낸다.

이를 재귀에 활용하여 짠 코드는 아래와 같다.

python 문제 풀이

# towerOfHanoi 함수에 N, a(시작기둥), b(목표기둥), c(보조기둥) 순으로 변수를 보낸다.
# towerOfHanoi(N, 1, 3, 2)로 보낸 것은 3번 기둥이 목적지이기 때문.

def towerOfHanoi(n, a, b, c):
    if n == 1:
        print(a, b)
        return
    
    if n > 1:
        towerOfHanoi(n-1, a, c, b)
        print(a, b)
        towerOfHanoi(n-1, c, b, a)

N = int(input())
count = 0
print(2**N - 1)
towerOfHanoi(N, 1, 3, 2)

참고

• 백준 11729번 : 통곡의 하노이 탑 (feat. python)
• [파이썬]알고리즘 이야기(01. 하노이 탑)