[알고리즘 일기] 5. 하노이의 탑

 

 

문제 05. (2021-05-05)

 

하노이의 탑

이 게임의 목표는 왼쪽 기둥에 있는 원판들을 모두 오른쪽 기둥으로 옮기는 것입니다. 탐색을 재귀로 구현해보세요.

하노이의 탑 - 위키백과, 우리 모두의 백과사전

 

주의사항

* 한 번에 하나의 원판만 옮길 수 있습니다.

* 큰 원판이 작은 원판 위에 있어서는 안 됩니다.

 

 

 

❧ 테스트 셋

def move_disk(disk_num, start_peg, end_peg):
    print("%d번 원판을 %d번 기둥에서 %d번 기둥으로 이동" % (disk_num, start_peg, end_peg))

def hanoi(num_disks, start_peg, end_peg):
    # Code

# Test
hanoi(3, 1, 3)

- num_disks : 원판 수

- start_peg : 게임을 시작하는 기둥 번호

- end_peg : 목표로 하는 기둥 번호

---

❧ 출력 예시

1번 원판을 1번 기둥에서 3번 기둥으로 이동
2번 원판을 1번 기둥에서 2번 기둥으로 이동
1번 원판을 3번 기둥에서 2번 기둥으로 이동
3번 원판을 1번 기둥에서 3번 기둥으로 이동
1번 원판을 2번 기둥에서 1번 기둥으로 이동
2번 원판을 2번 기둥에서 3번 기둥으로 이동
1번 원판을 1번 기둥에서 3번 기둥으로 이동

---

❧ 정답

def move_disk(disk_num, start_peg, end_peg):
    print("%d번 원판을 %d번 기둥에서 %d번 기둥으로 이동" % (disk_num, start_peg, end_peg))

def hanoi(num_disks, start_peg, end_peg):
    temp_peg = (6 - end_peg - start_peg)
    
    if num_disks == 1:
        return move_disk(num_disks, start_peg, end_peg)
    else:    
        hanoi(num_disks - 1, start_peg, temp_peg)
        move_disk(num_disks, start_peg, end_peg)
        hanoi(num_disks - 1, temp_peg, end_peg)

hanoi(3, 1, 3)

 

1️⃣ Recursive case

: 작은 부분으로 쪼개어 재귀적으로 푼다.

2️⃣ 가장 큰 원판을 제외한 n-1 개의 원판을 임시 기둥으로 옮긴다.

3️⃣ 가장 큰 원판을 시작 기둥에서 끝 기둥으로 옮긴다.

4️⃣ 나머지 원판 n-1 개의 원판을 임시 기둥에서 끝 기둥으로 옮긴다.

5️⃣ 함수(hanoi) 호출 시, 재귀적으로 내부 함수(hanoi) 2 번 호출

└ 시간 복잡도 : O(2n)

 

temp_peg 값 도출 방법

1(start_peg) 에서 2(end_peg)로 옮긴다면 tmp_peg는 3이 되어야하고

2(start_peg) 에서 3(end_peg)로 옮긴다면 tmp_peg는 1이 되어야한다.

1, 2, 3의 총 합은 항상 6이므로 6 - start_peg - end_peg 식이 도출 됨