[프로그래머스] 하노이의 탑

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

완전 탐색하여 최소의 값을 구하려 접근

조건이 까다로워 함수 구현이 어려움

 

재귀를 이용하여 접근

2) 알고리즘

• 재귀

3) 풀이 코드

사용 언어 - Python

def hanoi(n, start, middle, end, answer):       # 원반 개수(높이), 원반이 출발하는 기준 기둥, 중간 기둥, 목적지 기둥, 정답 리스트
    if n == 1:                                  # 현재 원반이 1층 높이(최상단이라 옮겨야 하는 경우)
        answer.append([start, end])             # 현재 기둥에서 목적지 기둥으로 옮김
        return
    
    hanoi(n-1, start, end, middle, answer)      # 지금 보고 있는 기둥에서 위에 원반선택, 목적지는 중간에 거쳐야 하는것으로 변경
    answer.append([start, end])                 # 위에 원반들을 모두 옮겼으니, 다음 원반 이동
    hanoi(n-1, middle, start, end, answer)      # 중간 기둥에 있는 원반을 옮기기 위해 재귀

def solution(n):
    answer = []                     # 원반 이동을 저장하는 리스트

    hanoi(n, 1, 2, 3, answer)       # 하노이 함수

    return answer


print(solution(3))

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

하노이의 탑 문제를 처음 접하여 재귀를 이용한 풀이로 접근하지 못함

재귀 호출을 알고 난 후에도 어떠한 방식으로 진행하는지 접근이 어려웠음

(1) 참고 사이트

• 블로그
  세개의 기둥을 이용해서 재귀를 들어갈때마다 파라미터 값인 세개의 기둥을 바꾸어 줌

2) 새롭게 학습한 내용

하노이의 탑을 풀기위한 재귀 호출 방법

---

🔗 문제 링크

- https://programmers.co.kr/learn/courses/30/lessons/12946

코딩테스트 연습 - 하노이의 탑

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다