파이썬 재귀호출 알고리즘 하노이의 탑 옮기기 #6

파이썬 재귀호출 알고리즘 하노이의 탑 옮기기 #6

안녕하세요.

 

인터넷이나 알고리즘 등에서 굉장히 유명한 문제 중 하나인 '하노이의 탑'을 재귀 호출을 통해 풀어 보도록 하겠습니다.

위와 같은 그림 많이 보셨을 텐데요.

 

A에 있는 1,2,3,4,5의 원반을 C로 옮기면 끝나는 문제 입니다.

 

간단한가요?

 

여기에는 규칙이 있습니다. 4가지 규칙이 있는데요.

 

1. 크기가 다른 원반 n개를 출발점 기둥(A)에서 도착점 기둥(C)로 전부 옮겨야 합니다.

2. 원반은 한 번에 한 개씩만 옮길 수 있습니다.

2. 원반을 옮길 때는 한 기둥의 맨 위 원반을 빼내어, 다른 기중의 맨 위로만 옮길 수 있습니다. 

4. 원반을 옮기는 과정에서 큰 원반을 작은 원반 위로 올릴 수 없습니다.

 

이 네가지 규칙을 지켜며 문제를 풀어 내면 됩니다.

 

케이스 별로 문제를 풀어 보겠습니다.

 

# 원반이 한 개일 때

1. A 기둥에서 C 기둥으로 바로 옮기면 됩니다.

 

# 원반이 두 개일 때

1. A 기둥의 맨 위에 있는 원반을 B 기둥으로 옮깁니다.

2. A 기둥에 남아 있는 큰 원반을 C 기둥으로 옮깁니다.

3. B 기둥에 남아 있는 원반을 C 기둥으로 옮깁니다.

 

# 원반이 세 개일 때

1. A 기둥에 잇는 원반 세 개 중에 위에 있는 원반 두 개를 비어 있는 B 기둥으로 옮깁니다. 앞에서 배운 2개의 원반을 옮기는 방법을 그대로 하면 됩니다. B 기둥을 보조 기둥으로 사용하여 A 기둥에 있는 원반 두 개를 B 기둥으로 옮기면 됩니다. A -> C, A -> B, C -> B

2. A 기둥에 남아 있는 큰 원반을 C 기둥으로 옮깁니다.

3. 이번에는 B 기둥에 있는 원반 두 개를 C 기둥으로 옮깁니다. 비어있는 A 기둥을 이용하여 2개를 옮기는 방법을 그대로 사용 하면 C로 옮기실 수 있습니다. B -> A, B -> C, A -> C

이렇게 총 7번의 이동으로 문제가 해결 되었습니다.

 

이런식으로 생각 해보면 원반이 n개일때의 알고리즘을 추론 할 수 있습니다.

 

# 원반이 n개 일때

1. A 기둥에 있는 n-1 개의 원반을 B 기둥으로 옮깁니다.

2. A 기둥에 남아 있는 원반중 가장 큰 원반을 C 기둥으로 옯깁니다.

3. B 기둥에 있는 n-1개 원반을 C 기둥으로 옮깁니다.

 

이 문제는 기본적으로 원반이 1개, 2개, 3개 일때 하나 더 작은 값의 알고리즘을 호출 하여 반복적으로 문제를 해결하는 재귀 호출 알고리즘에 해당 합니다.

 

어떤신가요? 감이 오시나요?

 

파이썬 소스를 한번 확인 해 볼까요?

# 하노이의 탑
# 입력: 옮기려는 원반의 갯수 n
#      옮길 원반이 현재 있는 출발점 기둥 from_pos
#      원반을 옮길 도착점 기둥 to_pos
#      옮기는 과정에서 사용할 보조 기둥 aux_pos
# 출력: 원반을 옮기는 순서 

def hanoi(n, from_pos, to_pos, aux_pos):
    if n == 1:  # 원반 한 개를 옮기는 문제면 그냥 옮기면 됨
        print(from_pos, "->", to_pos)
        return

    # 원반 n - 1개를 aux_pos로 이동(to_pos를 보조 기둥으로)
    hanoi(n - 1, from_pos, aux_pos, to_pos)
    # 가장 큰 원반을 목적지로 이동
    print(from_pos, "->", to_pos)
    # aux_pos에 있는 원반 n-1개를 목적지로 이동(from_pos를 보조 기둥으로)
    hanoi(n - 1, aux_pos, to_pos, from_pos)

print("n = 1")
hanoi(1, 1, 3, 2)  # 원반 한 개를 1번 기둥에서 3번 기둥으로 이동(2번을 보조 기둥으로)
print("n = 2")
hanoi(2, 1, 3, 2)  # 원반 두 개를 1번 기둥에서 3번 기둥으로 이동(2번을 보조 기둥으로)
print("n = 3")
hanoi(3, 1, 3, 2) # 원반 세 개를 1번 기둥에서 3번 기둥으로 이동(2번을 보조 기둥으로)

이해가 잘 되셨는지 모르겠습니다.

 

이렇게 오늘 하노이의 탑 알고리즘 포스팅을 마치겠습니다.

 

감사합니다.

 

# 본 포스팅은 도서출판 길벗의 모두의파이썬 X 알고리즘 을 참조 하였습니다.