[백준/파이썬] 11729번 하노이 탑 이동 순서 풀이
업데이트:
문제 정보
- 문제 출처: 백준 온라인 저지
- 문제 링크: 11729번 하노이 탑 이동 순서
- 문제풀이 코드 GitHub 링크
- 제출 언어: Python 3
풀이
문제
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.
- 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
- 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.
아래 그림은 원판이 5개인 경우의 예시이다.
- 자세한 문제 및 입출력 예제는 상단의 문제 출처(백준 홈페이지)를 참조해주세요
코드
import sys
def move(ea, src, by, dest):
if ea == 1:
global result
result.append(f'{src} {dest}\n')
return 1
else:
return move(ea-1, src, dest, by) + move(1, src, by, dest) + move(ea-1, by, src, dest)
result = []
print(move( int(sys.stdin.readline()), 1, 2, 3 ))
print("".join(result))
설명
유명한 하노이 탑 문제입니다.
이 문제를 풀기 전에 이해해야하는 것은, 재귀 호출은 메모리의 스택공간을 이용하게 된다는 점입니다. 또한, return move(ea-1, src, dest, by) + move(1, src, by, dest) + move(ea-1, by, src, dest)와 같은 문장이 있을 때, 세 함수를 순서대로 호출 하는 것이 아닌, 하나의 함수의 끝을 보고 나서야 다음 함수를 호출한다는 점도 아셔야합니다. 이 점을 이해하셔야, result 리스트에 어떻게 순서대로 결과가 저장될 수 있는지를 알 수 있습니다.
이러한 전제 조건을 이해하셨다면, 다음 설명을 하도록 하겠습니다.
move(ea, src, by, dest) 함수는 ea개의 원판을 src에서 by를 거쳐 dest로 옮기는 데 몇 단계가 필요한 지를 반환하고, 해당 과정을 전역 변수로 이용할 result리스트에 저장하는 역할을 합니다.
그렇다면 이 함수는 왜 이런모양이 되었는가? 그것을 이해하시려면, 하노이 탑의 풀이는 ‘n개의 원판을 움직이는 경우가 n-1개의 원판을 움직이는 경우의 확장판’ 이라는 데에 주목하셔야 합니다.
아래의 지렁이인지 그림인지 모를 무언가를 보시면 이해가 더 잘되실 거라 믿습니다
(↑ 1개의 원판일 경우)
(↑ 2개의 원판일 경우)
보시면, 2개의 원판의 경우
- 1개의 원판을 1에서 2로 옮긴다.
- 나머지 1개의 원판을 1에서 3으로 옮긴다.
- 1개의 원판을 2에서 3으로 옮긴다.
위와 같은 과정으로 이루어져 있음을 알 수 있습니다.
즉, 시작할 때 가장 아래에 있는 1개의 원판을 제외한 나머지 원판은 임시 저장소(2번)에 옮겨놓고, 현재 원판은 목적지(3번)에 옮기고, 다시 임시저장소(2번)에 있는 원판들을 목적지(3번)에 옮기는 방식으로 구할 수 있습니다.
일반화 해보면,
- n-1개의 원판을 1에서 2로 옮긴다.
- 나머지 1개의 원판을 1에서 3으로 옮긴다.
- n-1개의 원판을 2에서 3으로 옮긴다.
위와 같은 과정이 됩니다.
여기서, 1번 과정을 자세히 보면, 1이 출발지, 2가 목적지라는 점을 알 수 있습니다. 마찬가지로, 2번은 1이 출발지, 3은 목적지, 3번 과정은 2가 출발지, 3이 목적지가 됩니다.
출발지와 목적지가 아닌 나머지 한 곳이 임시저장소가 됩니다.
즉, 출발지(src), 거쳐야 할 곳(임시저장소, by), 목적지(dest) 3곳을 어떻게 선정했는지에 대한 정보가 필요합니다.
이 일반화 한 루틴과, 임계 조건(재귀 반복을 멈출 조건)인 1개의 원판을 움직일 때(그냥 바로 옮기면 됨. 옮기며 result에 기록하기)이 있으면 위와같은 재귀함수를 작성할 수 있습니다.
함수를 호출하고 나서 결과를 출력해주면 끝입니다.
댓글남기기