out_of_anjoong.dev

알고리즘 분류

- 재귀(recursion)

풀이

하노이 탑은 recursion을 공부할 때 꼭 구현해보는 문제인 것 같다. 
그만큼 loop 보다 recursion을 활용했을 때 깔끔한 코드를 작성할 수 있기 때문이다.
문제를 이해하는 데에 있어 구글링을 통해 직접 하노이 탑 플래쉬 게임을 해보는 것도 좋은 방법이다.

하노이 탑의 핵심은 가장 큰 원판을 이동시켜야 할 기둥(Pole 3)으로 가기 위해서는 가장 큰 원판을 제외한 나머지 원판들이 경유할 기둥(Pole 2)으로 다 이동하여야 한다는 것이다. 그리고 경유 기둥에 있는 원판들은 출발 기둥(Pole 1)을 경유 기둥으로 쓰는 것 역시 핵심 원리이다.

코드

def move(start, to, answer):
    answer.append([start, to])
def hanoi(n, start, to, via, answer):
    if n == 1:
        move(start, to, answer)
    else:
        hanoi(n - 1, start, via, to, answer)
        move(start, to, answer)
        hanoi(n - 1, via, to, start, answer)
def solution(n):
    answer = []
    hanoi(n, 1, 3, 2, answer)
    return answer

- move(start, to, answer) : 원판이 움직일 때 answer에 출발 기둥과 목적지 기둥을 기록한다.
- hanoi(n, start, to, via, answer) : 경유 기둥을 이용하여 n개의 원판을 start에서 to로 옮기기.