항해 TIL
def solution(n):
answer = []
def dfs(n, src, target, inter):
if n == 1:
answer.append([src, target])
else:
dfs(n-1, src, inter, target)
dfs(1, src, target, inter)
dfs(n-1, inter, target, src)
dfs(n, 1, 3, 2)
return answer
Python
복사
하노이는 사실 학부 때부터 볼 때마다 틀린 문제여서,
이번에 조금 극복해보기 위해 영상을 참고해서 풀어보았다.
하노이 탑 문제는 세 개의 기둥과 다양한 크기의 원반을 사용.
재귀적 방법을 사용하여 문제를 해결
•
n: 현재 이동해야 할 원반의 수
•
src: 출발 기둥 (source)
•
target: 목표 기둥 (target)
•
inter: 중간 기둥 (intermediate)
재귀 과정:
•
기본 케이스: n == 1일 때, 단순히 src에서 target으로 원반을 옮김.
◦
원반이 하나 일 때는 재귀의 기본 케이스로 향함
•
재귀 케이스: n > 1일 때, 다음 세 단계로 문제를 해결
◦
원반이 1개가 넘어가면
a. n-1개의 원반을 src에서 inter로 옮김.
b. 가장 큰 원반 1개를 src에서 target으로 옮김.
c. n-1개의 원반을 inter에서 target으로 옮김
•
각 이동은 [출발 기둥, 도착 기둥] 형태로 저장됨