#9. 하노이 타워 - HanoiTower

하노이 타워란?

원반을 한 번에 하나씩 옮기면서 최종적으로 초기 상태를 유지한 채로 두 칸 옆의 기둥으로 옮기는 퍼즐

이 퍼즐을 현실에서 푸는 동작은 사실 어렵지 않다.

문제는 이 과정에서 재귀의 특성을 찾고, 그걸 프로그래밍적으로 해결하는 것이다.

 

크기가 큰 순서부터 3, 2, 1 이라고 할 때

제일 먼저 해결해야 하는 것은 3 원반을 C로 옮기는 것. 다만 그렇게 하려니 2번과 1번을 B로 치워야 한다.

2번과 1번 원반을 옮기면, 또 1번을 C로 옮겨야 한다.

처음 이 문제를 보면서 프로그래밍적으로는 큰 문제를 해결하기 위해 작은 문제부터 해결하는 분할 정복(Divide/Conquer) 알고리즘을 사용해야 하나 싶었는데, 조금 다른 결의 풀이다. 

내가 생각했던 이유로는 4개의 원판이 있다고 했을 때 3개를 먼저 해결해야 하고, 3개를 먼저 해결하기 위해 2개를 해결해야 하는, 점점 작은 문제부터 풀어야 하는 과정이라고 생각해서 분할 정복을 떠올렸다.

 

물론 이 방법도 가능하긴 하겠지만, 재귀를 이용하면 더 쉽게 해결이 가능했다.

그림으로 이해해보자.

그림이 조금 조악하지만, 설명해보자면 다음과 같다.

가장 밑의 원반, 4 라고 불렀을 때 4는 결론적으로 C로 옮겨야 한다.

그러기 위해서는 위의 3, 2, 1 총 3개의 원반을 옮겨야 한다.

 

다시 반복해서, 3의 원반을 옮기기 위해서는 2, 1의 2개의 원반을 옮겨야 하고

2를 옮기기 위해서는 1만 옮기면 되는 과정이다.

 

여기까지가 4를 C로 옮기기 위한 동작인데, 결론적으로 그렇게 해결되고 나면 3, 2, 1 의 원반이 다시 한 층에 쌓여있게 된다.

이 3개의 원반은 또 어떻게 옮길까?

여기서 이제 재귀의 특성이 나온다.

3개의 원반은 방금 4를 C로 옮기는 동작에서 수행했던 과정이다. 그 과정을 그대로 반복하면 되는것이다.

 

재귀의 가장 강력한 특성으로

하나의 문제를 한 패턴을 통해 해결하고 나면, 파생적으로 발생하는 문제들이 자동 해결된다

가 있다.

 

하노이 타워의 일반화

일반화라고 해도 위에서 설명했던 과정을 하나씩 풀어서 숫자만 기호로 바꾼 것이다.

살펴보면 크게 어렵지 않다.

4개의 원반을 모두 C로 옮겨야 한다는 것은 퍼즐의 목적이다.

가장 처음 원반 4를 C로 옮기기 위해서 치워야 할 것이 3개의 원반 3, 2, 1, 이다.

이게 과정1이고,

그럼 남은 원반 4를 C로 옮길 수 있을 것이다.

이게 과정 2이다.

그리고 남은 원반 3, 2, 1을 C로 옮기기만 하면 퍼즐이 해결된다.

 

여기서 일반화를 위해 숫자 4를 n 으로 바꾸기만 한 것이다.

이걸 이게 코드로 풀어보자.

위에서 언급한 n 은 num, 원반의 갯수가 된다.

A, B, C의 기둥이 있는데 현재 있는 기둥이 from, 도달해야 하는 기둥이 to 가 된다.

그렇다면 by는 from 에서 to로 옮기는 동안 활용할 수 있는 남는 기둥 하나가 되는 것이다.

최종적으로는 이렇게 정리할 수 있다.

 

물론 이렇게만 적으면 무한루프를 방지하기 위한 탈출 코드가 없다.

탈출 조건으로는 이동할 원반이 남지 않은 상태, 즉 당장은 1개만 옮기면 되는 상태가 될 것이다.

 

이 조건까지 감안하고 코드를 작성하게 되면 다음과 같다.

void HanoiTowerMove(int num, char from, char by, char to)
{
	if (num == 1) std::cout << "원반1을 " << from << "에서 " << to << "로 이동" << std::endl;
	else
	{
		HanoiTowerMove(num-1, from, to, by);
		std::cout << "원반" << num << "을 " << from << "에서 " << to << "로 이동" << std::endl;
		HanoiTowerMove(num-1, by, from, to);
	}
}

C++로 작성하면서 Cout 부분이 보기 조금 번거롭게 됐지만, 결과는 문제없이 동작한다.

탈출 조건은 위에서 언급했듯이 원반을 1개만 옮기면 되는 상태, if(num == 1) 이 된다.

그 전까지는 저 과정 1, 2, 3을 계속 실행시켜주면 된다.

 

최종적으로 시행하기 위해 main 문까지 작성한 코드는 다음과 같다.

#include <iostream>

void HanoiTowerMove(int num, char from, char by, char to)
{
	if (num == 1) std::cout << "원반1을 " << from << "에서 " << to << "로 이동" << std::endl;
	else
	{
		HanoiTowerMove(num-1, from, to, by);
		std::cout << "원반" << num << "을 " << from << "에서 " << to << "로 이동" << std::endl;
		HanoiTowerMove(num-1, by, from, to);
	}
}

int main()
{
	HanoiTowerMove(5, 'a', 'b', 'c');

	return 0;
}

 

결과는 이렇게 출력된다.

원반의 갯수를 5개로 늘려서 시행했더니 줄이 길어졌지만, 실제로 하나하나 검수해본 결과 문제없이 동작한다.

 

이번 하노이 타워를 학습하면서도 느낀 것이지만, 문제를 해결할 때 눈 앞의 문제보다 과정들 사이의 흐름, 프로그래밍적으로는 코드 간의 시행 관계를 파악하는 것의 중요도를 더 높일 필요가 있어보인다.