❓백준 11729번 : 하노이의 탑 이동 순서
〽️ 문제 요약
1번, 2번, 3번 봉이 있는 하노이 탑에서 1번봉에 위치한 N개의 원판을 3번봉의 위치로 옮기기 위한 최소 횟수와 이때의 경로를 출력하면 되는 문제
🤨 접근법
문제를 풀이하기 전 한 블로그 포스트 ‘하노이의 탑’ 이해하기를 참고했다. 문제 자체를 이해하는 데에도 많은 도움이 되었지만, 재귀 문제를 해결하기 위해 접근하는 방법 자체를 배울 수 있었다.
먼저 하노이의 탑의 이동 과정을 살펴보자.
위와 같이 3개의 원판이 1에 있을 경우, 3위치에 전부 옮기기 위해서는 먼저 원판 3을 위치 3에 놓아야 한다. 이를 위해서 위치 2에 원판 1, 2를 옮겨야 한다. 즉, 원판 3개를 옮기기 위해서 그 위 원판 2개를 먼저 옮기는 과정이 수반된다는 것이다. 그 후 위치 1에 있는 원판 3을 위치 3으로 옮긴다.
그 다음은 위치 2에 있는 원판 2개를 위치 3에 옮기므로서 이동이 완료된다. 여기에서 원판 2개를 옮기는 과정이 다시 한번 나타난다.
이동이 완료되었다. 이제 코드를 설계해보자.
문제를 코드로 정의해 보면 이렇게 정의할 수 있다.
hanoi(N, start, to, via) : start에서 to로 via를 거쳐 N개의 원반을 이동할 때 이동 과정을 출력하라.
- 우리는 위치 1에 있는 원판 3개를 위치 2를 거쳐서 위치 3으로 옮겨야 한다.
hanoi(3, 1, 3, 2)- 이를 위해 위치 1에 있는 원판 2개를 위치 3을 거쳐서 위치 2로 옮겼다.
hanoi(2, 1, 2, 3) - 그리고 위치 1에 있는 원판 3을 위치 3으로 옮겼고,
move(1, 3) # print(1, 3) - 위치 2에 있는 원판 2개를 위치 3으로 옮겼다.
hanoi(2, 2, 3, 1) - 이제 이를 일반화 해보자.
🔡 코드
import sys
input = sys.stdin.readline
N = int(input().rstrip())
def hanoi(n, start, to, via):
if n == 1:
print(start, to)
else:
hanoi(n-1, start, via, to)
print(start, to)
hanoi(n-1, via, to, start)
print(2**N - 1)
hanoi(N, 1, 3, 2)n이 1인 경우 옮기기만 하면 되므로 다시 재귀 하지 않고 start부터 to까지 이동함을 출력함으로써 재귀를 종료할 수 있도록 한다.
하노이탑에서 원판이 이동하는 횟수는 하나의 함수가 두 번의 재귀식을 실행시키고 각각 한번씩 이동하게 된다. 여기서 2의 지수식이 나온다는 것을 알 수 있고, N=1일 때는 재귀한지 않고 1번만 이동하므로 총 번 이동함을 알 수 있다.
📚 고찰
문제에서 중복되는 문제가 발견되는 경우 재귀식을 세워서 코드로 설계하는 전반적인 과정을 제대로 경험할 수 있었던 문제였다. 재귀함수는 많은 경우에 재귀식을 표현만 할 수 있으면 그대로 풀린다는 것을 알았고, 설계가 코딩을 이긴다는 것을 알았다. 설계를 잘 한다면 코드로 구현하는 것은 쉬우니까.
