[백준] 11729 하노이 탑 이동 순서 (파이썬 Python)

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

11729번: 하노이 탑 이동 순서

문제 설명

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

1. 한 번에 한 개의 원판(맨 위의 원판)만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

---

풀이 과정

• 나의 풀이

 ① 이 문제에서 직관적으로 파악한 것은 '세 개의 장대가 고정적으로 주어져 있고 첫번째 장대의 원판들(원판 개수는 입력값으로 주어짐)이 세번째 장대로 이동할 때 이동 횟수와 이동 과정을 출력하는 거구나'이다.

 ② 이동 횟수의 경우 고등학교 수2에 공식으로 나와있었다-!-!

[사진출처] 네이버 블로그 <수학벙커, 수학을 낱낱이 까발리다> 

  따라서 이동 횟수는 2**입력값 - 1 로 출력해주면 된다.

③ 이 문제의 하이라이트라고도 할 수 있는 하노이탑 이동 과정을 어떻게 출력해야할지 생각해보자. 

 (1) 아이디어 열기

 언제나 문제를 작게 만들어 해결하고 이후 확대하는 것이 중요하기에 실제로 원반을 직접 이동시켜보면서 문제의 핵심 아이디어를 포착하여 보자.

[사진출처] https://shoark7.github.io/programming/algorithm/tower-of-hanoi

  위의 사진에서의 과정은 입력값이 3일 때, 즉 hanoi(3)의 이동과정을 나타낸 것이라고 할 수 있다.

 (2) 재귀....??

 재귀(recursion)란 같은 형태의 보다 작은 입력을 지닌 자기 자신을 호출하는 것이고, 이렇게 재귀적인 호출을 사용하는 함수를 재귀함수라고 한다. (1)에서 사진에서 보면 알 수 있듯이 1번과정으로 넘어갈 때는 이동의 시작기둥이 A, 보조기둥이 B, 도착기둥이 C임을 알 수 있다. 그리고 2번과정으로 넘어갈 때는 시작기둥이 A, 보조기둥이 C, 도착기둥이 B임을 알 수 있다. 이처럼 기둥의 역할만 달라질 뿐 실제로 원판이 이동하면서 hanoi(N)이었던것이 hanoi(N-1)으로 재귀되는 듯한 느낌을 충분히 받을 수 있을 것이다-!-!

 (3) 문제 분해

 이제 문제 해결을 위한 식을 대략적으로 만들면 다음과 같다.

 hanoi(N,start,via,to) # start에서 via를 거쳐 to로 총 N개의 원반을 운반할 때 각 이동 과정을 출력하라

 이후 실제 수식에 대해 생각해보자.

 ● hanoi(3,'A','B','C')

 ○ 첫번째 재귀 :  (1)의 그림에서 알 수 있듯이 첫번째 재귀로서 N-1개의 원판을 보조기둥 'B'로 옮긴다.

 ○ 두번째 재귀 :  N-1개의 원판을 'B'에서 'C'로 옮긴다.

 

 아하!!! 첫번째 재귀를 마치고 'A'에 있는 원판 하나를 'C'에 옮긴 후 두번째 재귀까지 마치면 해결되는 것이었다!!

 이를 실제 코드로 구현하면 다음과 같다.

# 11729
def hanoi_algorithm(n, from_, with_, to_): # n개의 원판을 from_에서 to_로 옮기는데 with_는 보조기둥임.
    if n == 1 :
        print(from_,to_)
    else :
        hanoi_algorithm(n-1, from_, to_, with_)
        print(from_,to_)
        hanoi_algorithm(n-1, with_, from_, to_)

n = int(input())
print(2**n-1)
hanoi_algorithm(n,1,2,3)

---

후기

 재귀문제를 쭉 풀다가 만난 첫번째 난관이었던 문제이다. 언제나 문제를 작게 만들어 해결하고 이후 확대하는 것이 중요하다는 것을 기억하며 문제의 유형 및 아이디어 파악이 너무나도 중요했던 문제이다.