Programmers / 하노이의 탑 / Python 파이썬

 

*문제 출처는 프로그래머스에 있습니다.

문제 제목: 하노이의 탑 (2단계)

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/12946

프로그래머스

---

이 글은 모두의 알고리즘 도서를 참고하여 작성한 게시글입니다. 사진의 저작권은 모두 모두의 알고리즘 출판사 길벗에 있음을 알립니다.

하노이의 탑 규칙

크기가 다른 원반 n개를 출발점 기둥에서 도착점 기둥으로 전부 옮겨야 합니다.

• 원반은 한 번에 한 개씩만 옮길 수 있습니다.

• 원반을 옮길 때는 한 기둥의 맨 위 원반을 뽑아, 다른 기둥의 맨 위로만 옮길 수 있습니다(기둥의 중간에서 원반을 빼내거나 빼낸 원반을 다른 기둥의 중간으로 끼워 넣을 수 없습니다).

• 원반을 옮기는 과정에서 큰 원반을 작은 원반 위로 올릴 수 없습니다.

 

그림 6-2   하노이의 탑 규칙

 

원반을 맨 위에서 하나씩만 꺼내서 옮겨야 한다는 제약이 없다면 원반을 한꺼번에 다 뽑아서 3번 기둥으로 옮기면 됩니다. 그리고 작은 원반 위에 큰 원반을 올릴 수 있다면 1번 기둥에 있는 원반을 하나씩 빼서 2번 기둥으로 다 옮긴 다음 다시 3번으로 옮기면 끝나는 간단한 문제입니다. 하지만 제약 사항을 지켜야 하므로 그렇게 간단히 끝나지는 않습니다.

그림 6-3   하노이의 탑 규칙 제대로 이해하기

 

하노이의 탑 풀이

◼︎ 원반이 한 개일 때

1번 기둥에 있는 원반을 3번 기둥으로 옮기면 끝납니다(1 → 3).

◼︎ 원반이 두 개일 때

➊ 1번 기둥의 맨 위에 있는 원반을 2번 기둥으로 옮깁니다(1 → 2).

그림 6-6   맨 위의 원반을 1에서 2로 이동

 

 

➋ 1번 기둥에 남아 있는 큰 원반을 3번 기둥으로 옮깁니다(1 → 3).

그림 6-7   남은 원반을 1에서 3으로 이동

 

 

➌ 2번 기둥에 남아 있는 원반을 3번 기둥으로 옮깁니다(2 → 3).

그림 6-8   2번 기둥의 원반을 2에서 3으로 이동

 

 

세 번 만에 원반 두 개를 원하는 곳으로 옮겼습니다.

 

◼︎ 원반이 세 개일 때

원반이 세 개일 때부터는 조금 더 생각을 해야 합니다. 원반이 세 개인 문제를 풀기 전에 원반이 두 개인 문제를 이미 풀었다는 사실을 꼭 기억해야 합니다. 즉, 우리는 특정 기둥에 있는 원반 두 개를 우리가 원하는 기둥으로 옮기는 방법을 이미 알고 있다는 것입니다.

 

➊ 1번 기둥에 있는 원반 세 개 중에 위에 있는 원반 두 개를 비어 있는 2번 기둥(보조 기둥)으로 옮깁니다. 하노이의 탑 규칙에 따르면 한 번에 원반을 두 개씩 옮길 수 없다고 했지만, 우리는 이미 원반이 두 개일 때 하노이의 탑을 푸는 방법을 알고 있으니 그 방법을 그대로 적용하면 됩니다. 3번 기둥을 보조 기둥으로 사용하여 1번 기둥에 있는 원반 두 개를 2번 기둥으로 옮기는 문제이므로 1 → 3, 1 → 2, 3 → 2 순서로 옮기면 됩니다(실제로 원반은 세 번 이동합니다).

 

그림 6-9   원반 두 개를 1에서 2로 이동(1 → 3, 1 → 2, 3 → 2)

 

 

➋ 1번 기둥에 남아 있는 큰 원반을 3번 기둥으로 옮깁니다(1 → 3).

 

그림 6-10   남은 원반을 1에서 3으로 이동

일단 중요 Point는 n-1번째까지의 원판을 모두 옮겨내야함!

그래야 제일큰 원판을 3번째 칸에 넣을 수 있다.

 

그럼 n = 3일 때는?

이렇게 start 의 위치가 바뀜

 

나의 풀이

def solution(n):
    def hanoi(n, start, target, Sub):
        if n == 1: # n=1일때는 그냥 원반을 옮기면 끝
            answer.append([start, target])
            return
        hanoi(n - 1, start, Sub, target) #target이 sub가 됨
        answer.append([start, target]) 
        hanoi(n - 1, Sub, target, start) #start가 sub가 됨
        
    answer = []
    hanoi(n, 1, 3, 2)
    return answer

 

---

※ 알아야 할 것

- start sub target의 위치가 바뀌면서 원반을 옮겨야함을 유의하자

- 제일 큰 원판을 Target에 옮겨야 한다!!! 그러면 문제가 수월하게 이해된다