문제 17 - 하노이의 탑 (Python)

프로그래머스

세 개의 기둥을 이용하여 원판을 조건에 맞게 목적지로 옮기는 퍼즐 문제입니다. 큰 문제를 작은 단위의 덩어리로 쪼개어 해결하는 재귀적 사고방식을 익히기에 가장 적합한 알고리즘입니다.

---

1.  나의 풀이

하노이의 탑 규칙인 '작은 원판 위에 큰 원판이 올 수 없다'는 제약을 지키며 전체 원판을 옮기기 위해, 가장 큰 원판을 제외한 나머지 원판들을 하나의 '덩어리'로 취급하여 이동시키는 재귀 로직을 사용했습니다.

def hanoi(n, start, to, mid, answer):
    # 옮겨야 할 원판이 1개인 경우 바로 목적지로 이동
    if n == 1:
        answer.append([start, to])
        return

    # 1. n-1개의 원판 덩어리를 목적지를 경유지로 삼아 이동
    hanoi(n - 1, start, mid, to, answer)
    
    # 2. 가장 아래에 있는 가장 큰 원판(n)을 목적지로 이동
    answer.append([start, to])
    
    # 3. 경유지에 있던 n-1개의 원판 덩어리를 다시 목적지로 이동
    hanoi(n - 1, mid, to, start, answer)


def solution(n):
    answer = []
    # 1번 기둥에서 3번 기둥으로, 2번 기둥을 경유하여 이동 시작
    hanoi(n, 1, 3, 2, answer)
    return answer

---

2.  오늘 배운 점 및 복기 노트

추상화와 덩어리 중심의 사고

재귀 함수를 설계할 때 가장 중요한 것은 모든 이동 경로를 하나씩 추적하려는 유혹을 버리는 것입니다. 가장 큰 원판 \( n \)을 목적지로 보내기 위해, 그 위에 쌓인 \( n-1 \)개의 원판을 하나의 '덩어리'로 인식하는 추상화 작업이 필요합니다. 이 덩어리가 다시 내부적으로 더 작은 덩어리로 쪼개지며 결국 원판 1개(\( n=1 \))라는 최소 단위에 도달할 때까지 재귀가 반복됩니다.

반복문 풀이와의 로직 차이

이전에는 반복문을 사용하여 홀수와 짝수에 따른 기둥 이동 규칙(Modulo 연산)을 직접 계산하여 문제를 해결했습니다. 반복문 방식은 매 순간 "다음에 이동할 원판은 무엇인가"를 직접 결정해야 하므로 구현이 매우 복잡해집니다. 반면 재귀 방식은 "가장 큰 것을 옮기기 위해 위쪽 덩어리를 치운다"는 구조적 논리에만 집중하면 나머지는 호출 스택이 자동으로 관리해줍니다.

 

반복문 풀이

def solution(n):
    answer = []
    # 실제 원판의 위치를 관리하는 타워 리스트 생성
    tower = [[i for i in range(n, 0, -1)], [], []]
    # 원판 개수가 짝수인지 홀수인지에 따라 첫 번째 고정 기둥 인덱스 설정
    fixed_tower_idx = 2 if n % 2 == 0 else 1

    while len(tower[2]) < n:
        # 고정된 기둥을 제외한 나머지 두 기둥 사이에서 이동 가능한 원판 탐색
        ta_idx = (fixed_tower_idx + 1) % 3
        ta = tower[ta_idx]
        tb_idx = (fixed_tower_idx + 2) % 3
        tb = tower[tb_idx]

        if not ta:
            ta.append(tb.pop())
            answer.append([tb_idx + 1, ta_idx + 1])
        elif not tb:
            tb.append(ta.pop())
            answer.append([ta_idx + 1, tb_idx + 1])
        elif ta[-1] < tb[-1]:
            tb.append(ta.pop())
            answer.append([ta_idx + 1, tb_idx + 1])
        elif tb[-1] < ta[-1]:
            ta.append(tb.pop())
            answer.append([tb_idx + 1, ta_idx + 1])
        
        # 기둥 이동 규칙에 따라 고정 기둥 인덱스 업데이트
        fixed_tower_idx = (fixed_tower_idx - 1 if n % 2 == 0 else fixed_tower_idx + 1) % 3

    return answer

반복문 방식은 fixed_tower_idx와 Modulo 연산을 사용하여 물리적인 원판의 이동을 시뮬레이션해야 하므로 로직이 매우 복잡합니다. 반면 재귀 방식은 "가장 큰 것을 옮기기 위해 위쪽 덩어리를 치운다"는 구조적 논리에만 집중하면 나머지는 호출 스택이 자동으로 관리해 줍니다.

 

기둥의 역할 전이

재귀 호출이 일어날 때마다 start, to, mid 인자에 전달되는 기둥 번호가 바뀝니다. 이는 현재 다루고 있는 원판 덩어리를 기준으로 기둥의 목적과 역할이 매 순간 재정의되기 때문입니다. $n-1$개를 치울 때는 기존의 경유지가 목적지가 되고, 치웠던 것을 다시 가져올 때는 기존의 시작지가 경유지가 되는 유연한 역할 교체를 이해했습니다.

---

3.  프로그래머스 코딩 테스트 문제 풀이 전략 교재에서 배울만한 점

점화식 수립을 통한 논리적 증명

재귀 문제는 수학적 귀납법과 유사한 흐름을 가집니다. \( f(1) \)이 참이고, \( f(n-1) \)이 성립한다고 가정했을 때 \( f(n) \)을 만드는 논리를 세우는 것입니다. 하노이의 탑은 \( 2 \times hanoi(n-1) + 1 \)이라는 명확한 이동 횟수 점화식을 가지며, 이를 코드로 옮기는 과정에서 가설 검증의 중요성을 배울 수 있습니다.

상태를 인자로 관리하는 효율성

반복문에서는 tower라는 중첩 리스트를 만들어 직접 pop과 append를 하며 원판의 실제 위치를 시뮬레이션했습니다. 그러나 교재의 재귀 풀이는 원판의 물리적 위치를 배열로 관리하지 않고, 오직 함수의 인자를 통해 논리적 흐름만을 전달합니다. 이는 메모리 관리 측면에서 불필요한 데이터 조작을 줄이고 핵심 로직에만 집중하게 만드는 파이썬다운 효율적인 접근 방식입니다.