- 엘리스 자료구조의 정석) 문제
하노이의 탑
재귀알고리즘을 이용해 풀 수 있는 문제로는 하노이의 탑 이라는 퍼즐이 있습니다.
3개의 막대가 있고 가장 왼쪽 막대에는 탑의 높이만큼의 원반이 가장 큰 것부터 차례로 쌓여 있습니다.
이 하노이의 탑의 목표는 다음과 같은 조건을 지키면서 가장 왼쪽막대의 원반을 모두 가장 오른쪽으로 이동하는 것입니다.
- 한번에는 하나의 원반만 이동할 수 있습니다.
- 가장 위에 있는 원반만 이동할 수 있으며 가장 위에만 내려놓을 수 있고 중간에 끼워 넣을 수 없습니다.
- 큰 원반은 작은 원반 위로 갈 수 없습니다.
함수 hanoi에 탑의 높이가 입력으로 들어오면 3번으로 모든 원반을 옮기기 위해 몇 번째 기둥의 원반을 몇 번째 기둥으로 옮겨야 하는지에 대한 리스트를 반환하는 코드를 작성해 봅시다.
예를 들어 2가 입력으로 들어왔다면
[ (1, 2), (1, 3), (2, 3)]을, 3이 입력으로 들어왔다면 [ (1, 3), (1, 2), (3, 2), (1, 3), (2, 1), (2, 3), (1, 3)] 으로 이동해야 합니다.
- 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
def hanoi(height) :
result = []
def move(n,start,end):
if n<1:
return
move(n-1,start,6-start-end)
result.append((start,end))
move(n-1,6-start-end,end)
# 여기에 재귀 알고리즘을 구현 해 봅시다.
move(height,1,3)
return result
def main():
print(hanoi(3))
if __name__ == "__main__":
main()
|
cs |
- 이번 알고리즘을 통해 배운 점
하노이탑은 전에 배운적이 있었음에도 했갈렸다.
하노이의 탑은 (2의 n승) -1 만큼 옮겨야 한다. 예를 들어 n=3, 7개
A B C
간단히 설명하면
해당 이미지 처럼 먼저 판을 A에서 B로
이후 B에서 C로 옮기면 되는 것이다.
그림과 같이 A->C로 갈때와 A->B로 갈때와 B->C 는 동작 방식이 유사하다.
단 옮길 때마다 N-1개라는 것만 제외하면 말이다.
동작 방식: 출발지점에서 도착지점으로 가기위해서는 가장 밑에 있는 원판이 도착지점으로 갈 때까지
나머지 원판들이 보조지점으로 가야한다.*반복
즉 A->C로 가기 위한 동작 방식으로는 A->B로 가는 동작 방식과 B->C로 가는 동작 방식이 필요하다는 말이다.
최종 정리 : A->C로 가는 함수는 두번의 재귀함수를 통해 동작한다! 단 재귀에서는 옮길 때 N-1개를 해줘야 한다.
그래서 하노이탑에서는 재귀함수를 쓴다.
* 6-start-end는 단순히 sub를 대체하기 위한 값
1. A->B
move(n-1,start,6-start-end)
= move(n-1,start,sub,end)
2. B->C
move(n-1,6-start-end,end)
= move(n-1,sub,end,start)
'Python > 백준 알고리즘 (파이썬)' 카테고리의 다른 글
[프로그래머스] 신고 결과 받기 (2) | 2023.07.12 |
---|---|
[프로그래머스] 달리기 경주 (0) | 2023.07.12 |
동적 계획법 practice_02 가장 큰 부분 합 찾기 (0) | 2022.06.23 |
동적 계획법 practice01_1로 만들기 (0) | 2022.06.22 |
브루트 포스 practice 03_ 덩치 (0) | 2021.08.11 |