[백준 BOJ_11729] 하노이 탑 이동 순서 Python 풀이

출처: 백준 온라인 저지

문제

풀이

하노이 탑에서는 출발지, 경유지, 목적지의 개념이 중요합니다.
결과적으로는 출발지가 1번, 경유지가 2번, 목적지가 3번이 됩니다.

먼저 N=1의 경우에는 상관없이 1번에서 3번으로 옮길 수 있습니다.

N=2의 경우에는

1. 1번에서 1개를 2번에 먼저 옮긴 뒤
2. 1번에서 다음 1개를 3번에 옮긴 뒤
3. 2번에서 마지막 1개를 3번에 옮겨줍니다.

여기까진 간단해보이지만 다음부터 복잡해집니다.

N=3의 경우:

1. 1번에서 1개를 3번에 먼저 옮긴 뒤
2. 1번에서 다음 1개를 2번에 옮긴 뒤
3. 3번에서 1개를 2번에 옮긴 뒤
4. 1번에서 남은 1개를 3번에 옮긴 뒤
5. 2번에서 1개를 1번에 옮긴 뒤
6. 2번에서 남은 1개를 3번에 옮긴 뒤
7. 1번에서 마지막 1개를 3번에 옮겨줍니다.

간단하게 이해하기 위해 위의 경우를 간추려 보겠습니다.

1 ~ 3 과정은 1번에서 2번으로 2개를 옮기는 과정이라고 생각하고,
4번은 그저 1개를 옮기는 과정이며,
5 ~ 7 과정은 또 다시 2번에서 3번으로 2개를 옮기는 과정이라 생각한다면

• 1번에서 2개를 2번에 먼저 옮긴 뒤
• 1번에서 1개를 3번에 옮긴 뒤
• 2번에서 다시 2개를 3번에 옮기면 됩니다.

위의 과정을 다시 N에 대해 출발지, 경유지, 목적지 개념을 더해 정리한다면:

• 1번(출발지)에서 N-1개를 2번(목적지)에 먼저 옮긴 뒤 (3번이 경유지)
• 1번에서 1개를 3번에 옮긴 뒤 (기저 사례)
• 2번(출발지)에서 다시 N-1개를 3번(목적지)에 옮기면 됩니다. (1번이 경유지)

코드

def move(n, start, end, stopover):
    if n == 1:
        print(start, end) # 1개일 때는 고민없이 목적지에 옮겨주기
        return
    move(n-1, start, stopover, end) # 1번(출발지) 2번(목적지) 3번(경유지)
    print(start, end)
    move(n-1, stopover, end, start) # 2번(출발지) 3번(목적지) 2번(경유지)
    return

N = int(input())
print(2**N - 1)
move(N, 1, 3, 2)