하노이 타워 알고리즘과 파이썬 소스 코드

얼마전 네이버캐스트에서 소개된 하노이의 탑 문제로 알아보는 재귀 알고리즘을 읽어보고 글을 씁니다(http://navercast.naver.com/contents.nhn?rid=2871&contents_id=87713)

인터페이스가 가장 괜찮은 하노이의 탑 플래쉬 게임: http://www.gamegape.com/ko-65022-tower-of-hanoi.html

링크의 네이버캐스트 글에서는 원판을 모두 옮기는 데 소모되는 이동 횟수에 주목하고 있습니다.

이 글에서는 하노이 타워 문제를 푸는 알고리즘에 집중해보겠습니다.

너무 너무 재미있는 하노이의 탑을 푸는 알고리즘을 알아봅시다.

원판이 서너 개 정도까지는 직관적으로 풀 수 있습니다.

풀이 방법은 위 유투브 비디오의 Yusuf Shakee님의 설명을 참고하였습니다.

먼저 하노이 타워에 관하여 알아봅시다.

하노이 타워는 매우 유명한 게임입니다. 이 게임은 세 개의 기둥(peg)과 N개의 원판(disk)으로 이루어져 있습니다. 그리고, N개의 원판은 가장 앞의 기둥에 크기의 내림차순으로 아래부터 쌓여 있습니다. 이 게임의 목표는 가장 앞 기둥에서 가장 뒷 기둥으로 모든 원판을 옮기는 것입니다. 이 때, 한 가지 제약 조건이 있습니다. 바로 큰 원판은 작은 원판 위에 있을 수 없습니다.

하노이의 탑 문제를 풀기 위해서는 재귀적인 방법으로 풀 수 있습니다.

일반적으로 사용하는 용어에 관해 정의하겠습니다.

T(N, Beg, Aux, End)

T: 풀이 절차의 단계를 나타내는 수

N: 원판의 수

Beg: 시작 기둥

Aux: 임시 기둥

End: 목표 기둥

풀이 절차

1. T(N-1, Beg, End, Aux)

2. T(1, Beg, Aux, End)

3. T(N-1, Aux, Beg, End)

1단계에서는 가장 위의 (N-1) 원판을 시작 기둥에서 임시 기둥으로 옮깁니다.

2단계에서는 1 원판을 시작 기둥에서 목표 기둥으로 옮깁니다.

3단계에서는 가장 위의 (N-1) 원판을 임시 기둥에서 목표 기둥으로 옮깁니다.

N이 1일 때는 Beg에서 End로 원판을 옮깁니다.

하노이의 탑 가장 쉬운 문제인 원판 세 개 부터 시작합시다.

N = 3 이므로

T(3, A, B, C)

부터 시작합니다(시작 기둥: A, 임시 기둥: B, 목표 기둥: C).

재귀적 문제 풀이 방법인 아래의 풀이 절차를 따라가겠습니다.

1단계: T(N-1, Beg, End, Aux)

2단계: T(1, Beg, Aux, End)

3단계: T(N-1, Aux, Beg, End)

T(3, A, B, C)

N = 3

Beg = A

Aux = B

End = C

이므로

1단계 T(N-1, Beg, End, Aux)에 T(3, A, B, C)를 적용하면,

T(2, A, C, B)를 얻습니다.

2단계 T(1, Beg, Aux, End)에 T(3, A, B, C)를 적용하면,

T(1, A, B, C)를 얻습니다. 이는 A에서 C로 옮겨라는 의미입니다(A -> C).

3단계 T(N-1, Aux, Beg, End)에 다시 T(3, A, B, C)를 적용하면

T(2, B, A, C)를 얻습니다.

1단계에서 얻은 T(2, A, C, B)에서 다시 위 1, 2, 3단계를 적용합니다.

1단계 T(N-1, Beg, End, Aux)에 T(2, A, C, B)를 적용하면,

T(1, A, B, C)를 얻습니다. 이는 A에서 C로 옮겨라는 의미입니다(A -> B).

2단계 T(1, Beg, Aux, End)에 T(2, A, C, B)를 적용하면,

T(1, A, C, B)를 얻습니다. 이는 A에서 B로 옮겨라는 의미입니다(A -> B).

3단계 T(N-1, Aux, Beg, End)에 T(2, A, C, B)를 적용하면,

T(1, C, A, B)를 얻습니다. 이는 C를 B로 옮겨라는 의미입니다(C -> B).

가장 처음에 얻은 2단계에서 N = 1이므로 건너뜁니다.

가장 처음 3단계에서 얻은 결과인 T(2, B, A, C)로 다시 갑니다.

1단계 T(N-1, Beg, End, Aux)에 T(2, B, A, C)를 적용하면,

T(1, B, C, A)를 얻습니다. 이는 B를 A로 옮겨라는 의미입니다.

2단계 T(1, Beg, Aux, End)에 T(2, B, A, C)를 적용하면,

T(1, B, A, C)를 얻습니다. 이는 B를 C로 옮겨라는 의미입니다(B -> C).

3단계 T(N-1, Aux, Beg, End)에 T(2, B, A, C)를 적용하면,

T(1, A, B, C)를 얻습니다. 이는 A를 C로 옮겨라는 의미입니다(A -> C).

[그림 1. 풀이 결과]

그림 1의 풀이 결과를 적용하여 원판을 옮깁니다.

이 때 중요한 점은 풀이 결과를 순차적으로 적용하는 것이 아니고, 나무 형태로 열거 되어 있다는 점입니다.

파이썬으로 프로그래밍하면 다음과 같은 함수로 나타낼 수 있습니다.

def T(N, Beg, Aux, End):

if N == 1:

print(Beg, '->', End)

else:

T(N-1, Beg, End, Aux)

T(1, Beg, Aux, End)

T(N-1, Aux, Beg, End)

실행해보면, 

>>> T(3, 'A', 'B', 'C')

A -> C

A -> B

C -> B

A -> C

B -> A

B -> C

A -> C

>>> 

>>> T(7, 'A', 'B', 'C')

A -> C

A -> B

C -> B

A -> C

B -> A

B -> C

A -> C

A -> B

C -> B

C -> A

B -> A

C -> B

A -> C

A -> B

C -> B

A -> C

B -> A

B -> C

A -> C

B -> A

C -> B

C -> A

B -> A

B -> C

A -> C

A -> B

C -> B

A -> C

B -> A

B -> C

A -> C

A -> B

C -> B

C -> A

B -> A

C -> B

A -> C

A -> B

C -> B

C -> A

B -> A

B -> C

A -> C

B -> A

C -> B

C -> A

B -> A

C -> B

A -> C

A -> B

C -> B

A -> C

B -> A

B -> C

A -> C

A -> B

C -> B

C -> A

B -> A

C -> B

A -> C

A -> B

C -> B

A -> C

B -> A

B -> C

A -> C

B -> A

C -> B

C -> A

B -> A

B -> C

A -> C

A -> B

C -> B

A -> C

B -> A

B -> C

A -> C

B -> A

C -> B

C -> A

B -> A

C -> B

A -> C

A -> B

C -> B

C -> A

B -> A

B -> C

A -> C

B -> A

C -> B

C -> A

B -> A

B -> C

A -> C

A -> B

C -> B

A -> C

B -> A

B -> C

A -> C

A -> B

C -> B

C -> A

B -> A

C -> B

A -> C

A -> B

C -> B

A -> C

B -> A

B -> C

A -> C

B -> A

C -> B

C -> A

B -> A

B -> C

A -> C

A -> B

C -> B

A -> C

B -> A

B -> C

A -> C

>>> 

어때요? 재밌죠?