해당 게시글에서는 [백준] 11729 하노이 탑 이동 순서 문제를 해설하고 Python을 이용하여 풀고자 한다.
💡 문제 풀이
11729번 문제는 재귀(recursion)로 유명한 하노이 탑 문제에 해당한다.
해당 문제에서는 입력된 초기 원판의 개수에 대해 하노이 탑 규칙에 따라 모든 원판을 이동시킬 때 옮긴 횟수(K)와 이동 경로를 출력해야 한다.
하노이 탑을 재귀적으로 구현하기 위해 원판 개수에 따라 반복되는 과정이 있는지 고민하는 시간을 가졌으며, 그 결과는 다음과 같다.
- N개의 원판을 모두 옮기기 위해, 먼저 N-1개의 원판(가장 큰 원판을 제외한 나머지)을 다른 장대로 옮긴다.
- 가장 큰 원판을 세 번째 장대로 옮긴다.
- 이전에 옮긴 N-1개의 원판을 세 번째 장대로 옮긴다.
위의 내용을 통해 재귀적으로 코드를 작성하면 다음과 같다. 자세한 코드는 아래를 참고하길 바란다.
1
2
3
hanoi(N-1, start, end, via) # N-1개의 원판 이동
hanoi(1, start, via, end) # 가장 큰 원판 이동
hanoi(N-1, via, start, end) # N-1개의 원판을 가장 큰 원판 위로 이동
📂 코드
- start: 시작하는 장대
- via: 경유하는 장대
- end: 최종으로 모든 원판이 도착하는 장대 ```python global move move = []
def hanoi(N, start, via, end): “”” :param N: 원판의 수 :param start: 시작 기둥 :param via: 중간 기둥 :param end: 끝 기둥 :return: 이동 횟수 “”” if N <= 1: # 원판이 1개 있는 경우 move.append((start, end)) return 1
1
2
3
4
5
cnt = 0
cnt += hanoi(N-1, start, end, via) # N-1개의 원판을 보조 기둥에 모두 이동
cnt += hanoi(1, start, via, end) # 가장 큰 원판을 끝 기둥에 이동
cnt += hanoi(N-1, via, start, end) # N-1개의 원판을 끝 기둥에 이동
return cnt
print(hanoi(int(input()), 1, 2, 3)) for f, t in move: print(f, t)
```