재귀 함수 practice01_하노이탑

 

- 엘리스 자료구조의 정석) 문제

 

하노이의 탑

재귀알고리즘을 이용해 풀 수 있는 문제로는 하노이의 탑 이라는 퍼즐이 있습니다.

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)] 으로 이동해야 합니다.

 

 

- 코드

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()
 

 

- 이번 알고리즘을 통해 배운 점

 

 

하노이탑은 전에 배운적이 있었음에도 했갈렸다.

하노이의 탑은 (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)