[백준/Python] 11729 하노이 탑 이동 순서

[백준/Python] 11729 하노이 탑 이동 순서

정답 코드 및 설명

def hanoi(n, start, end, aux):
    if n == 1:
        print(start, end)
        return
    # n-1개의 원판을 aux 장대로 이동
    hanoi(n-1, start, aux, end)
    # 가장 큰 원판을 목적지로 이동
    print(start, end)
    # n-1개의 원판을 aux 장대에서 목적지로 이동
    hanoi(n-1, aux, end, start)

N = int(input())
# 옮긴 횟수는 2^N - 1
print(2**N - 1)
hanoi(N, 1, 3, 2)

문제 개념 설명

하노이 탑 문제는 재귀적 사고를 이해하고 적용하는 데 아주 좋은 예제다. 이 문제에서는 n개의 원판을 첫 번째 장대에서 세 번째 장대로 옮기는 과정을 최소 횟수로 수행해야 한다.

이때 두 가지 규칙을 따라야 한다:

1. 한 번에 한 개의 원판만 옮길 수 있다.
2. 큰 원판 위에 작은 원판이 올라갈 수 없다.

접근 방법

하노이 탑 문제를 해결하는 핵심 아이디어는 크게 세 단계로 나눌 수 있다:

1. n-1개의 원판을 첫 번째 장대에서 두 번째 장대로 이동한다. 이 과정에서 세 번째 장대를 보조 장대로 사용한다.
2. 남은 가장 큰 원판을 첫 번째 장대에서 세 번째 장대로 이동한다.
3. n-1개의 원판을 두 번째 장대에서 세 번째 장대로 이동한다.
   이때 첫 번째 장대를 보조 장대로 사용한다.

이 과정을 재귀적으로 수행하며, 원판의 개수가 1개일 때까지 반복한다. 원판이 1개인 경우는 간단히 해당 원판을 목적지 장대로 옮기면 된다.

코드 설명

• hanoi 함수는 n개의 원판을 start 장대에서 end 장대로 이동하는 과정을 출력한다. aux는 보조 장대의 역할을 한다.
  if n == 1: 조건에서는 원판이 1개인 경우 바로 end 장대로 옮긴다.
• 첫 번째 호출 hanoi(n-1, start, aux, end)는 n-1개의 원판을 첫 번째 장대에서 보조 장대(aux)로 이동한다.
• print(start, end)는 가장 큰 원판을 목적지 장대로 옮기는 과정을 출력한다.
• 마지막 호출 hanoi(n-1, aux, end, start)는 n-1개의 원판을 보조 장대에서 최종 목적지 장대로 이동한다.