문제
https://www.acmicpc.net/problem/11729
11729번: 하노이 탑 이동 순서
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로
www.acmicpc.net
하노이의 탑에서 이동 경로와 최종 이동 횟수를 출력하시오. (입력: 원판 개수)
Reference
https://ko.wikipedia.org/wiki/하노이의_탑
하노이의 탑 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 하노이의 탑(Tower of Hanoi)은 퍼즐의 일종이다. 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들
ko.wikipedia.org
https://shoark7.github.io/programming/algorithm/tower-of-hanoi
'하노이의 탑' 이해하기
'하노이의 탑' 문제를 이해하고 문제 해결을 위한 핵심 통찰을 살핀 뒤 코드로 작성합니다. 이후 탑의 개수에 따른 총 이동 횟수를 구하는 일반항까지 수학적으로 유도합니다.
shoark7.github.io
재귀 함수 - 하노이의 탑
읽기 전 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다. 개인적으로 사용해보면서 배운 점을 정리한 글입니다. PS 문제를 풀다보니 stack 학습 이후 재귀 풀이에 극도로 취
8iggy.tistory.com
https://soohyun6879.tistory.com/m/190
[백준/Python] 하노이 탑 이동 순서
https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승
soohyun6879.tistory.com
풀이
정말 의외로 심플하게 풀렸다. (실화)
하노이의 탑?
퍼즐 게임이다. 막대기 세 개와 크기가 다른 원판이 있고 이걸 맨 끝에 있는 막대로 옮기면 되는데 규칙이 있다.
1. 원판은 한번에 하나씩 옮길 수 있다.
2. 원판은 맨 위에 것만 옮길 수 있다.
3. 큰 원판이 작은 원판 위에 오면 안된다.
참 쉽죠?
def hanoi(number_of_disks_to_move, from_, to_, via_):
if number_of_disks_to_move == 1:
print(from_, "->", to_)
else:
hanoi(number_of_disks_to_move-1, from_, via_, to_)
print(from_, "->", to_)
hanoi(number_of_disks_to_move-1, via_, to_, from_)
하노이의 탑 코드를 보면 이렇게 입력 인자가 4개이다. (원판 개수, 어디서, 어디로, 어디를 통해) 개수 말고 세 개는 시작 기둥, 끝 기둥, 보조 기둥이다. 그럼 입력인자 다이어트가 되나요?
import sys
a = int(sys.stdin.readline())
def hanoi(n,start,to,via):
if n == 1:
print('{} {}'.format(start,to))
else:
hanoi(n-1,start,via,to)
print('{} {}'.format(start,to))
hanoi(n-1,via,to,start)
print(2 ** a - 1)
hanoi(a,1,3,2)
아뇨 그냥 입력인자 중 기둥을 고정값으로 두시면 됩니다. 이동 횟수도 재귀하면서 셀 필요 없이 2^n-1 하면 된다. (n=원판 개수)
'BOJ > [BOJ] Python' 카테고리의 다른 글
백준 2231번 풀이 (0) | 2022.08.19 |
---|---|
백준 2798번 풀이 (0) | 2022.08.19 |
백준 2477번 풀이 (0) | 2022.08.19 |
백준 2447번 풀이 (0) | 2022.08.19 |
백준 17478번 풀이 (0) | 2022.08.19 |