[크래프톤 정글] 백준 1914번 하노이의 탑

오늘은 1914번 하노이의 탑 문제의 풀이에 대해 정리해 보려 한다. 문제를 보자

하노이의 탑 문제 접근법 정리

하노이의 탑 문제는 주어진 규칙에 따라 원반들을 다른 기둥으로 옮기는 문제다. 이 문제는 주로 재귀적 접근법을 사용하여 해결할 수 있다. 목표는 최소한의 이동 횟수로 모든 원반을 목적지 기둥으로 옮기는 것이다.

1. 문제 설명

하노이의 탑 문제는 세 개의 기둥(A, B, C)과 크기가 다른 ( N )개의 원반이 있는 상황을 가정한다. 모든 원반은 처음에 첫 번째 기둥(A)에 쌓여 있고, 크기가 큰 원반이 아래에 위치하며 크기가 작은 원반이 위에 위치한다. 목표는 다음 두 가지 규칙을 준수하며 첫 번째 기둥(A)에서 세 번째 기둥(C)로 모든 원반을 옮기는 것이다.

• 한 번에 한 개의 원반만 옮길 수 있다.
• 크기가 작은 원반은 크기가 큰 원반 위에 놓일 수 없다.

2. 문제 해결을 위한 기본 아이디어

하노이의 탑 문제는 재귀적으로 해결할 수 있다. 원반의 개수를 ( N )개로 가정할 때, 문제를 작은 문제로 나누어 해결할 수 있다.

1. 가장 큰 원반(즉, ( N )번째 원반)을 옮기기 위해서는 그 위의 ( N-1 )개의 원반을 중간 기둥으로 옮겨야 한다.
2. 가장 큰 원반을 출발지 기둥에서 목표 기둥으로 옮길 수 있다.
3. 중간 기둥에 있는 ( N-1 )개의 원반을 목표 기둥으로 옮길 수 있다.
4. 문제에서의 기둥을 스택이라고 생각하면 각 원반의 이동을 이해하는데 도움이된다. 실제로 하노이의 탑을 구현 해야한다면 스택을 통해 구현 할수 있다.

이 과정을 재귀적으로 반복하여 문제를 해결할 수 있다.

하노이의 탑 문제의 재귀적 동작 순서

1. 첫 번째 호출: hanoi(3, A, C, B)
   • 목표: A에 있는 3개의 원반을 C로 옮기는 것.
   • 이 호출에서 첫 번째 단계는 hanoi(2, A, B, C)를 호출하여, 가장 큰 원반(3번 원반)을 제외한 2개의 원반을 A에서 B로 옮기는 것이다.
2. 내부 재귀 호출: hanoi(2, A, B, C)
   • 목표: A에 있는 2개의 원반을 B로 옮기는 것.
   • 이 호출에서 다시 첫 번째 단계로 hanoi(1, A, C, B)를 호출하여 가장 작은 원반(1번 원반)을 A에서 C로 옮긴다.
   • 1번 원반을 C로 옮긴 후, 두 번째 단계로 2번 원반을 A에서 B로 옮긴다.
   • 마지막으로 hanoi(1, C, B, A)를 호출하여 C에 있는 1번 원반을 B로 옮긴다.
   • 이제 hanoi(2, A, B, C) 호출이 완료되고, 모든 원반이 A에서 B로 옮겨진다.
3. 본 호출로 돌아오면: hanoi(3, A, C, B)
   • hanoi(2, A, B, C)가 리턴되면, 본 호출인 hanoi(3, A, C, B)에서는 이미 n-1개의 원반(1번, 2번 원반)이 보조 기둥 B로 이동되었다고 생각하고 다음 단계를 수행한다.
   • 따라서, 본 호출의 다음 단계로 가장 큰 원반(3번 원반)을 A에서 C로 옮긴다.
4. 남은 재귀 호출:
   • 마지막으로, hanoi(3, A, C, B)는 세 번째 단계인 hanoi(2, B, C, A)를 호출하여, 보조 기둥 B에 있는 n-1개의 원반(1번, 2번 원반)을 목표 기둥 C로 옮긴다.

요약

• hanoi(3, A, C, B)를 호출했을 때, 내부에서 hanoi(2, A, B, C)를 호출하고 리턴되면:
  • 본 호출(hanoi(3, A, C, B))에서는 n-1개의 원반(즉, 1번과 2번 원반)이 보조 기둥 B로 이동된 상태라고 가정하고, 문제를 계속 풀어 나가야 한다.
• 이는 내부에서 이루어지는 모든 재귀적 호출 에서 동일하다. 모든 재귀 호출에서 탈출 조건에 부합 하지 않는 한 다시 내부에서 재귀를 호출하게 되는데 해당 호출이 리턴 된 후 부터는 , 이동된 상태라고 생각하고 다음 로직을 써야 한다는것이다.
• 이처럼 재귀적 호출에서 작은 문제를 해결하고 나면, 다음 단계로 큰 원반을 목표 기둥으로 옮기고, 마지막으로 다시 작은 문제를 해결하는 방식으로 문제를 이어나간다.

구현

def hanoi(n, source, target, auxiliary):  
    if n == 1:  
        # 원판을 source에서 target으로 옮긴다.  
        print(source, target)  
        return

    # Step 1: n-1개의 원판을 source에서 auxiliary로 옮긴다.
    hanoi(n - 1, source, auxiliary, target)

    # Step 2: 가장 큰 원판을 source에서 target으로 옮긴다.
    print(source, target)

    # Step 3: n-1개의 원판을 auxiliary에서 target으로 옮긴다.    
    hanoi(n - 1, auxiliary, target, source)

# 입력 처리

N = int(input())

# 하노이의 탑 문제 해결 및 출력

print(2 ** N - 1) # 최소 이동 횟수  
if N <= 20:

hanoi(N, 1, 3, 2)