얼마전 네이버캐스트에서 소개된 하노이의 탑 문제로 알아보는 재귀 알고리즘을 읽어보고 글을 씁니다(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
>>> 

어때요? 재밌죠?


신고
Posted by 공돌이pooh

댓글을 달아 주세요

  1. 2017.10.08 16:14  댓글주소  수정/삭제  댓글쓰기

    비밀댓글입니다

    • Favicon of http://woongheelee.com BlogIcon 공돌이pooh 2017.10.09 08:30 신고  댓글주소  수정/삭제

      안녕하세요.

      위 코드는 화면에 원판을 옮기는 순서를 나타내는 코드구요.

      링크의 웹 사이트를 들어가보니 문제에서 2차원 배열을 리턴해주어야 합니다.

      2차원 배열을 리턴해줄 수 있도록 코드를 수정하셔야 할 듯 하네요.

      그리고 해당 에러가 나타나는 이유는 제 글의 함수가 3개의 인자를 입력받아야 하는데, 그게 없어서입니다.

      참고: https://stackoverflow.com/questions/41133807/init-missing-3-required-positional-arguments

    • 세리 2017.10.09 15:32 신고  댓글주소  수정/삭제

      그렇군요! 감사합니다. 위 코드에 사용된 알고리즘 원리는 재귀함수. 조건문 인가요?

    • Favicon of http://woongheelee.com BlogIcon 공돌이pooh 2017.10.11 05:25 신고  댓글주소  수정/삭제

      넵, 맞습니다!