하노이의 탑 알고리즘 - 재귀함수

하노이의 탑은 퍼즐의 일종이다. 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다.

 

게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것이다.

 

즉 왼쪽의 원판들을 전부 오른쪽 기둥으로 순서 그대로 옮기는 것이다. 

 

원판의 숫자가 얼마나 커져도 상관없이 하나의 알고리즘으로 해결이 가능하다. 간단한 파이썬으로 구현할 수 있다.

 

그전에 재귀함수의 원리에 대해서 알아보자.

 

재귀함수는 함수를 정의함에 있어 본인 스스로를 재참조하여 정의하는 함수이다. 

 

예를 들어

 

숫자를 세는 함수로 순서를 따라가면

 

5 -> 4 -> 3 -> 2 -> 1 -> exit 가 출력이 된다, 결론적으로 맨 마지막의 조건에 맞는 함수가 호출될 때까지 본인 스스로를 계속 호출하는 함수이다.

 

물론 print(n)이 CountDown(n)함수보다 아래 있었다면 출력 순서는 반대일 것이다.

 

이러한 원리로 하노이의 탑 알고리즘을 풀어본다.

 

하노이의 탑은 실제로 게임을 진행하다 보면 일정한 규칙이 존재한다. 그 규칙이 알고리즘이며 그 알고리즘을 찾아서

구현하는 것이 목표이다.

 

기둥이 총 3개가 존재하여 1번 2번 3번 기둥이라고 지칭하고 원판을 A, B, C라고 3가지만 두고 예를 들어보겠다.

 

 

 

 

A
B
C
1기둥	2기둥	3기둥

 이라고 가정한다.

 

제일 위의 A원판의 선택지는 2와 3이 존재하고 1차적인 목표는 C가 3번 기둥에 제일 먼저 안착해야 한다.

 

1. A원판이 2번 기둥으로 먼저 이동한다고 가정한다.

     

B
C	A
1기둥	2기둥	3기둥

 

1-2. 그럼 당연히 B원판은 A원판보다 크기가 크기 때문에 3번 기둥으로 이동할 수 밖에 없다.

C	A	B
1기둥	2기둥	3기둥

1-3. C원판은 이동할 공간이 없고 A원판은 C원판 위로 이동하게 되면 C원판이 움직일 수 없으니 B원판 위로 이동할 수 밖에 없다.

		A
C		B
1기둥	2기둥	3기둥

1-4. 그러면 C원판은 2기둥으로 밖에 이동할 수 없고 최소한의 움직임으로 C기둥을 먼저 3기둥으로 보내야하는 1차 조건에 부합하지 않는다.

 

그러면 맨 위의 처음 A원판은 무조건 2기둥이 아닌 C원판이 가야할 곳으로 이동을 해야 한다. 

 

2-1. A원판이 C원판의 목표 기둥으로 이동한다.

B
C		A
1기둥	2기둥	3기둥

2-2. 남은 기둥에 B원판이 이동한다. 그러면 A원판은 B원판보다 작기 때문에 2기둥으로 움직일 수 있고 자연스레 3기둥으로 C원판이 이동 가능하게 된다.

C	B	A
1기둥	2기둥	3기둥

	A
C	B
1기둥	2기둥	3기둥

	A
	B	C
1기둥	2기둥	3기둥

2-3. 남은 두 원판을 3기둥으로 차례차례 올리기 위해서 A원판이 먼저 1기둥으로 이동하고 B원판이 그 다음 3기둥으로 이동하고 나머지 A원판이 3기둥으로 이동하면 하노이 탑 3개 원판이 끝난다.

A	B	C
1기둥	2기둥	3기둥

		B
A		C
1기둥	2기둥	3기둥

		A
		B
		C
1기둥	2기둥	3기둥

그럼 문제는 여기서 이 일부 사례를 보고 규칙화하여 하나의 알고리즘으로 코딩하는 것이 목표이다.

 

여기서 규칙화 할 수 있는 점들을 짚고 가보자. 다만 예시를 3개로 들었기 때문에 직관성이 떨어질 수 있다.

5개의 원판을 예시로 들면 맨 위 3개의 원판이 먼저 3기둥으로 이동하고 4번째 원판이 2번 기둥 그리고 똑같이 3기둥의 3개 원판이 2기둥위로 쌓이고 맨 마지막 5번 원판이 3기둥으로 이동하게 되고 다시 반복하면 된다. 

 

옮겨야할 디스크가 아무리 많아도 위의 디스크를 먼저 다 옮기고 행위를 반복하면 되기 때문에 N개의 디스크를 옮긴다고 가정하면 N-1개, N-2개, N-3, N-4 ······· 3개 디스크를 옮기면 되는 것이다. 

 

그렇다면 함수는

move_disk(N)

    조건

    디스크 이동

    move_disk(N-1) 이 될 것이다.

 

이동하는 함수가 재귀함수가 되어 맨 모든 원판이 3기둥으로 이동하도록 조건을 걸면 된다.

구현한 코드는 아래와 같다.

 

1. 처음 원판(1)은 무조건 목표가 되는 원판(맨 아래 원판)이 가야하는 마지막 기둥으로 옮긴다.

2. 다음 원판(2)은 처음 원판(1)이 존재하는 마지막 기둥으로 옮길 수 없으니 중간 기둥으로 옮긴다 즉 두번째(-1)기둥으로 옮긴다.

3. 마지막 원판(3)이 마지막 기둥으로 가기 위해 처음 원판(1)은 중간기둥으로 이동, 마지막 원판(3)은 목표 기둥으로 이동

4. 다시 중간 기둥의 원판들이 마지막 기둥으로 이동하기 위해 처음 원판(1)은 처음 기둥으로 이동, 다음 원판(2)은 마지막 기둥으로 이동, 처음 원판(1)도 마지막 기둥으로 이동하면 된다.

 

이 4가지의 단계를 재귀함수로 구현하면 위의 함수와 같다. 

 

하나의 함수를 호출하고 그 함수가 본인 스스로를 어떤 조건이 될 때까지 끊임 없이 호출하고 맨 마지막에 호출한 함수부터 실행되는 단계이다.