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

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

 

문제

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

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

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

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

입력

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

출력

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

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

예제 입력 1 

3

예제 출력 1 

7
1 3
1 2
3 2
1 3
2 1
2 3
1 3

첫 번째 제출 코드 (정답)

import sys
# N번 원판을 start에서 dst로 옮긴다
def move(N, start, dst):
    print(start, dst)
    return

# N번의 원판을 start에서 출발하여 via를 통해 dst로 옮긴다
def hanoi(N, start, via, dst):
    if N == 1:
        move(1, start, dst)
        return

    hanoi(N - 1, start, dst, via)
    move(N, start, dst)
    hanoi(N - 1, via, start, dst)
    return

N = int(sys.stdin.readline())
K = 2**N-1
print(K)
hanoi(N, 1, 2, 3)

하노이 탑 함수는 다음과 같은 재귀 함수로 이루어져 있습니다.

1. N번 원형 판 위에 있는 N-1개의 원판을 1에서 2로 옮깁니다.

2. N번 원형 판을 1번에서 3번으로 옮깁니다.

3. 아까 옮긴 N-1개의 원판을 N번 원형 판 위에 올립니다. 즉, 2에서 3으로 옮깁니다.

 

N개의 hanoi 타워를 옮기는 함수를 hanoi라고 하면 hanoi 타워는 다음과 같습니다.

hanoi(N, start, via, dst) #N개의 판을 start에서 시작하여 via를 통해 dst로 옮깁니다.

실질적으로 원형 판을 옮기는 함수 move는 다음과 같습니다.

move(N, start, dst) # N번 원형 판을 start에서 dst로 옮깁니다.

사실 위 문제는 move에서 N이 필요하지는 않습니다. 하지만 하노이 타워를 이해하는데 큰 도움이 될 수 있다고 생각해서 넣어주었습니다.

그리고 N=1 일 때만 실질적으로 옮겨줍니다. 

 

결과 및 정리

사실 재귀가 취약하다고 알고 있었지만 매번 다른 문제가 중요하다는 식으로 재귀 문제를 회피하였습니다.

하지만 다른 문제들을 어느 정도 풀고 보니 남은 게 재귀밖에 없어서 재귀를 오늘 제대로 이해하겠다고 생각하고 하노이 타워를 풀었습니다. 하지만 이 문제를 풀 때 손도 못 데서 검색을 통해 재귀적 접근법과 풀이방법을 배웠습니다.

 

제가 배운 사이트는 https://shoark7.github.io/programming/algorithm/tower-of-hanoi 여기입니다.

정말 처음부터 끝까지 설명을 잘해주셔서 한 번에 하노이 타워뿐만 아니라 재귀를 제대로 이해할 수 있었습니다.

게다가 제가 코딩을 하면서 느꼈지만 잘 고치려고 노력하지 않았던 설계 없이 코딩을 하는 문제를 콕 짚어 주셨습니다. 설계하는 방법을 잘 몰라 설계 없이 주먹구구 식의 코딩을 했는데 재귀를 통한 설계하는 과정까지 보여주셔서 설계의 방향을 잡는데도 큰 도움을 얻었습니다. 

 

위 글을 정독 한번하고 단번에 정답을 맞추었는데 너무 신기했고 기뻤고 재귀에 대한 자신감을 얻었습니다.

다음에는 스스로 재귀 문제를 설계부터 답까지 모두 맞춰보고 싶습니다.

화이팅!