Programmers / 하노이의 탑 / Python 파이썬
*문제 출처는 프로그래머스에 있습니다.
문제 제목: 하노이의 탑 (2단계)
문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/12946
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
이 글은 모두의 알고리즘 도서를 참고하여 작성한 게시글입니다. 사진의 저작권은 모두 모두의 알고리즘 출판사 길벗에 있음을 알립니다.
하노이의 탑 규칙
크기가 다른 원반 n개를 출발점 기둥에서 도착점 기둥으로 전부 옮겨야 합니다.
• 원반은 한 번에 한 개씩만 옮길 수 있습니다.
• 원반을 옮길 때는 한 기둥의 맨 위 원반을 뽑아, 다른 기둥의 맨 위로만 옮길 수 있습니다(기둥의 중간에서 원반을 빼내거나 빼낸 원반을 다른 기둥의 중간으로 끼워 넣을 수 없습니다).
• 원반을 옮기는 과정에서 큰 원반을 작은 원반 위로 올릴 수 없습니다.
원반을 맨 위에서 하나씩만 꺼내서 옮겨야 한다는 제약이 없다면 원반을 한꺼번에 다 뽑아서 3번 기둥으로 옮기면 됩니다. 그리고 작은 원반 위에 큰 원반을 올릴 수 있다면 1번 기둥에 있는 원반을 하나씩 빼서 2번 기둥으로 다 옮긴 다음 다시 3번으로 옮기면 끝나는 간단한 문제입니다. 하지만 제약 사항을 지켜야 하므로 그렇게 간단히 끝나지는 않습니다.
하노이의 탑 풀이
◼︎ 원반이 한 개일 때
1번 기둥에 있는 원반을 3번 기둥으로 옮기면 끝납니다(1 → 3).
◼︎ 원반이 두 개일 때
➊ 1번 기둥의 맨 위에 있는 원반을 2번 기둥으로 옮깁니다(1 → 2).
➋ 1번 기둥에 남아 있는 큰 원반을 3번 기둥으로 옮깁니다(1 → 3).
➌ 2번 기둥에 남아 있는 원반을 3번 기둥으로 옮깁니다(2 → 3).
세 번 만에 원반 두 개를 원하는 곳으로 옮겼습니다.
◼︎ 원반이 세 개일 때
원반이 세 개일 때부터는 조금 더 생각을 해야 합니다. 원반이 세 개인 문제를 풀기 전에 원반이 두 개인 문제를 이미 풀었다는 사실을 꼭 기억해야 합니다. 즉, 우리는 특정 기둥에 있는 원반 두 개를 우리가 원하는 기둥으로 옮기는 방법을 이미 알고 있다는 것입니다.
➊ 1번 기둥에 있는 원반 세 개 중에 위에 있는 원반 두 개를 비어 있는 2번 기둥(보조 기둥)으로 옮깁니다. 하노이의 탑 규칙에 따르면 한 번에 원반을 두 개씩 옮길 수 없다고 했지만, 우리는 이미 원반이 두 개일 때 하노이의 탑을 푸는 방법을 알고 있으니 그 방법을 그대로 적용하면 됩니다. 3번 기둥을 보조 기둥으로 사용하여 1번 기둥에 있는 원반 두 개를 2번 기둥으로 옮기는 문제이므로 1 → 3, 1 → 2, 3 → 2 순서로 옮기면 됩니다(실제로 원반은 세 번 이동합니다).
➋ 1번 기둥에 남아 있는 큰 원반을 3번 기둥으로 옮깁니다(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에 옮겨야 한다!!! 그러면 문제가 수월하게 이해된다