프로그래머스 Lv2 하노이의 탑 (python)

하노이의 탑

풀이

재귀로 풀어야 된다는 것도 알고 있었고, 이전 홀수나 짝수에 쓰였던 값이 다음 홀수, 짝수 값에서 재사용된 다는 것도 알고 있었지만, 어떻게 구현을 해야 하는지 계속 골골대다가 결국은 힌트를 보고 풀었다.
아직 내 머리는 이런 알고리즘들을 제대로 구현해내는 것이 불가능한가... 더 빨리 성장시켜서 예전에 이 정도는 껌으로 풀던 시절로 돌아가야지.

내 기존 풀이법은 완전탐색처럼 하는 방법이었으나, 그러니까 재귀함수가 너무 깊이 들어가서 실패를 계속했다. 그러다 보니 내가 바라보던 풀이 방식에서는 풀리지가 않았다.
그래서 힌트를 찾아보니 아래처럼 풀어야하는 것이 정석인 듯했다.
후.... 코드가 엄청 짧은 것을 보니 아직 내 실력은 한참이군.. 흑 잘 키우던 캐릭터가 사망하고 1 레벨부터 다시 키우려는 느낌으로 제대로 배워야지.

hanoi라는 함수를 따로 생성해주었다. 이때 매개변수는 원판의 개수, 시작지점, 옮길 지점, 나머지 기둥, 결괏값으로 되어있다.
결괏값은 이 문제에서 원하는 기둥에서 기둥으로 옮긴 기록이다.
1. hanoi 함수에서 원판이 1개 남았으면, 이 원판만 옮기면 되므로, 이를 end 칸으로 이동시킨다.
2. 이외는 옮기려는 칸 위치에 있는 것을 잉여 칸으로 옮기도록 한다.
3. 2. 가 끝나면, 옮김을 기록하고, 잉여 칸에서 목표 칸으로 원판을 이동시킨다.
4. 위를 반복하고 재귀가 끝났을 때의 result를 반환시킨다.

def hanoi(n, start, end, middle, result):
    # 원판이 한 개 남았으면 얘만 옮기면 됨
    if n == 1:
        # 해당 원판을 옮긴 판 위치에서 목표 칸으로 이동
        result.append([start, end])
        return None
    # n-1개의 원판을 옮긴 판 위치 에서 잉여 칸으로 이동
    hanoi(n - 1, start, middle, end, result)
    # 재귀에서 n == 1을 거치고 나온 시점이여서 n이 1개. 2개. 3개.... 있을 때 즉, 이전 내용을 입력받을 수 있음
    result.append([start, end])
    # n-1개의 원판을 잉여 칸 에서 목표 칸으로 이동
    hanoi(n - 1, middle, end, start, result)

def solution(n):
    # 원판의 이동 경로를 저장할 리스트
    result = []
    hanoi(n, 1, 3, 2, result)
    return result

나중에 다시 복습으로 풀어봐야 될 문제다. 재귀를 그래도 쓸 줄 안다고 생각했는데... 아직 멀었다.