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

문제 설명

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

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

n개의 원판을 i번째 기둥에서 j번째 기둥까지 옮기는 방법을 구하는 문제이다. 위의 프로그래머스 문제에서는 n개의 원판을 첫번째 기둥에서 세번째 기둥으로 옮기는 방법을 구하는 문제로 출제되었음. 하노이의 탑은 재귀로 풀이 가능한 전형적인 문제.

---

문제 접근

처음에 패턴을 파악해서 재귀로 연관지을 수 있는지가 포인트. 또한, 어디로 옮기든 옮기는 방식은 동일하다는 점을 빠르게 파악해야 함. 풀면서 어떤 식으로 재귀로 구현할 수 있을지가 감이 잘 안와서 헤맸음.

n개의 원판을 옮기기 위해서는 n-1개의 원판을 중간 기둥까지 옮겨야 하고, 1번 기둥에서 3번 기둥으로 n번째 원판을 옮긴다. 다시 중간 기둥에 위치한 n-1개의 원판을 3번 기둥으로 옮기면, n개의 원판을 옮기는 데 성공한다.

n-1개의 원판을 중간 기둥인 2번 기둥까지 옮기는 과정과 2번 기둥에 위치한 n-1개의 원판을 3번 기둥으로 옮기는 과정은 이전에 n-1개의 원판을 1번에서 3번으로 옮기는 것과 동일한 방식. 단순히 출발 기둥과 도착 기둥의 위치가 변화했을 뿐임. 

예컨대, n=3일 때 함수 호출은 3번 일어나게 된다.

① 2개의 원판을 1번에서 2번으로 이동 (재귀 호출)
② 3번째 원판을 1번에서 3번으로 이동
③ 2개의 원판을 2번에서 3번으로 이동 (재귀 호출)

이를 n개로 일반화하면 다음과 같다.

① n-1개의 원판을 출발 기둥에서 중간 기둥으로 이동 (재귀 호출)
② n번째 원판을 출발 기둥에서 도착 기둥으로 이동
③ n-1개의 원판을 중간 기둥에서 도착 기둥으로 이동 (재귀 호출)

위를 함수로 도식화해주면 된다. 출발, 중간, 도착의 3가지 인자 + 몇 개의 원판을 이동할 건지 (n) → 총 4가지를 인자로 받는 hanoi 함수를 정의해주면 된다.

한편, 재귀 호출에서 가장 중요한 것은 재귀 종료 조건이다. 여기서는 n = 1인 경우이며, 문제의 요구 조건에 맞춰 이동 순서를 담는 배열에 [출발 기둥, 도착 기둥]의 리스트를 삽입해주면 된다.

---

풀이

위의 접근을 코드로 정리하면, 아래와 같다.

# 하노이의 탑
def solution(n):
    answer = []
    
    def hanoi(src, tgt, inter, n): # 인자 순서 넣어주는 게 좀 헷갈렸음.
        if n == 1:
            answer.append([src, tgt])
        else:
            hanoi(src,inter,tgt,n-1)
            hanoi(src,tgt,inter,1)
            hanoi(inter,tgt,src,n-1)
            
    hanoi(1,3,2,n)
    
    return answer

처음에 출발, 도착, 중간을 아예 하드코딩으로 박아버려서 결과값이 이상하게 나왔는데...어찌저찌 잘 해결했다. 출발, 도착, 중간의 인자로 넣어주고 함수 호출 시 이의 순서를 잘 고려하면 함수 구현에는 어려운 점은 없을 듯하다.

---

정리

하노이의 탑은 개인적으로 까다로운 문제라고 생각한다..나에겐...재귀는 너무 어렵다. 하여튼, 무작정 하노이의 탑을 풀어내는 것보다는 문제를 직접 몇 개 풀면서 어느 정도 반복되는 패턴을 잡아내는 게 가장 중요한 것 같다. 재귀로 풀이하는 함수가 다 그렇겠지만..그 후에는 어떤 식으로 함수를 구현할지를 잘 생각해야할 듯하다.
하노이의 탑 문제 접근 방식은 칸 아카데미에서 많은 도움을 받았다. 그리고 직접 그려보는 게 제일 중요할 것 같다. 

개인적으로 헤맸던 점

• 재귀 패턴 찾기
• 위치에 상관없이 원판을 이동시키는 방식은 동일하다는 점
• 함수 인자 지정해주기 (중간 기둥)

 

Reference

1. https://ko.khanacademy.org/computing/computer-science/algorithms/towers-of-hanoi/a/towers-of-hanoi
2. https://ko.khanacademy.org/computing/computer-science/algorithms/towers-of-hanoi/a/towers-of-hanoi-continued