[BOJ / 파이썬] 11729: 하노이 탑 이동 순서

백준 / BOJ / Python / 파이썬

문제 링크 : https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

단계 : 재귀

알고리즘 분류 : 재귀

 

풀이:

재귀 하면 떠오르는 대표적인 문제 중 하나인 하노 이탑이다. 하노이 탑은 1, 2, 3번 기둥을 이용하여 1번 기둥에 있던 탑을 3번 기둥으로 원판 순서에 맞게 옮기는 문제이다.

해당 문제를 풀기 위해서는 "어떻게 하면 하노이탑을 옮길 수 있는가?"를 생각해야 한다. 하노이 탑에서 중요한 점은 크기가 큰 원판이 크기가 작은 원판의 위에 놓이지 못한다는 것이다. 이를 생각해볼 때 n개의 원판이 있을 때(작은 것부터 1 ... 가장 큰게 n) 가장 먼저 3번 기둥에 자리잡아야 하는 것은 n번째 원판이며 그 위로는 n-1번째 원판이 놓여야 한다.

 

이를 잘 생각해보면 높이 n의 하노이 탑이 3번 기둥에 옮겨가기 위해서는 높이 n-1의 하노이 탑이 먼저 2번 기둥에 옮겨가야한다. 이러한 점을 이용하여 우리는 n번째 원판을 src(출발지)에서 dst(도착지)로 옮기는 과정을 하기 전에 n-1번째 원판을 출발지에서 temp(나머지 : 기둥 번호의 합이 1+2+3 = 6 이므로 6에서 src와 dst를 빼면 남은 기둥의 번호를 구할 수 있다)옮겨야 한다. 해당 과정이 완료되면 n번째 원판을 dst로 옮길 수 있는 것이니 그때 print를 해주며 그 이후 n 기준 temp의 위치에 쌓여있는 n-1 높이의 탑을 dst로 옮겨주기 위해 재귀 함수를 사용한다.

코드

def hanoi(n, src, dst):
    temp = 6 - src - dst
    if n == 0:
        return
    hanoi(n - 1, src, temp)
    print(src, dst)
    hanoi(n - 1, temp, dst)


n = int(input())
print(pow(2, n) - 1)
hanoi(n, 1, 3)