[Data Structures][02-3] 하노이 타워 : The Tower of Hanoi

본 글은 윤성우의 열혈 자료구조 책을 읽고, 강의를 수강하고 복습한 것을 기록한 글입니다.

강의 교안 또한 참고하여 작성하였습니다.

(강의 교안의 경우 오렌지 미디어에서 다운로드할 수 있습니다)

목차
Chapter 02. 재 귀(Recursion)

Chapter 02-3: 하노이 타워 : The Tower of Hanoi

- 하노이 타워 문제의 이해

- 하노이 타워 문제 해결의 예

- 반복되는 일련의 과정을 찾기 위한 힌트

- 하노이 타워의 반복 패턴 연구

- 하노이 타워 문제의 해결

하노이 타워 : The Tower of Hanoi

함수의 호출 순서를 파악하고 이해하려고 하면 정말 어려워서 이해하기 힘들다. 이제부터는 함수의 호출 관계를 파악하고 문제에 대한 해결책을 찾고 코드로 작성하자.

하노이 타워 문제의 이해

원반을 A에서 C로 이동시키기

하노이 타워 문제 자체는 해결하기 어렵지 않지만, 프로그램으로 작성하고 구현하여 문제를 해결하는데 어려운 것이다.

제약사항

1. 원반은 한 번에 하나씩만 옮길 수 있습니다.

2. 옮기는 과정에서 작은 원반 위에 큰 원반이 올려져서는 안 됩니다.

하노이 타워 문제 해결의 예

지금 보인 과정에서 반복의 패턴을 찾아야 문제의 해결을 위한 코드를 작성할 수 있다!

반복되는 일련의 과정을 찾기 위한 힌트

위와 아래의 두 예를 통해서 문제의 해결에 있어서 반복이 되는 패턴이 있음을 알 수 있다.

하노이 타워의 반복 패턴 연구

목적. 원반 4개를 A에서 C로 이동

=> 큰 원반 n개를 A에서 C로 이동

1. 작은 원반 3개를 A에서 B로 이동

=> 작은 원반 n-1개를 A에서 B로 이동

2. 큰 원반 1개를 A에서 C로 이동

=> 큰 원반 1개를 A에서 C로 이동

3. 작은 원반 3개를 B에서 C로 이동

=> 작은 원반 n-1개를 B에서 C로 이동

하노이 타워 문제의 해결

하노이 타워 함수의 기본 골격

호출 함수 간의 관계를 보면 0번을 해결하기 위해서 1, 2, 3번의 일련의 과정이 필요한 것을 알 수 있다. 각각의 조건 안을 들여다 보아도 동일한 0번 조건에 의해 실행된다. 각각의 함수는 바로 HanoiTowerMove이기 때문이다. 그러므로 동일한 함수가 탈출 조건을 만나기 전까지 여러 번 호출되게 된다.

그리고 1번에서 by위치와 to 위치가 변하는 이유는 하노이 타워 규칙을 지키기 위해서이다. by 위치에 n-1개가 있는 상태에서 3번 조건을 통해서 다시 to위치, 우리가 최종적으로 원하는 위치에 다시금 원반을 옮기게 된다.

하노이 타워 함수 구현

void HanoiTowerMove(int num, char form, char by, char to)
{
	if(num == 1)	// 이동할 원반의 수가 1개라면
    {
    	printf("원반 1을 %c에서 %c로 이동 \n", from, to);
    }
    else
    {
    	HanoiTowerMove(num-1, from, to, by);
        printf("원반 %d을(를) %c에서 %c로 이동 \n", num, from, to);
        HanoiTowerMove(num-1, by, from, to);
    }
}

int main(void)
{
	// 막대 A의 원반 3개를 막대B를 경유하여 막대C로 옮기기
    HanoiTowerMove(3, 'A', 'B', 'C');
    return 0;
}

아래 결과에서 보이듯이 함수가 여러 번 호출되며 호출된 함수가 탈출 조건을 만나기 전까지 또 호출되게 코드가 구성되어있는 것을 확인할 수 있다. 위 코드를 작성할 때 아래 결과처럼 호출 순서를 생각하면 끝도 없지만, 재귀적으로 반복적인 패턴을 보이는 것을 잡아 내고 호출 함수 간의 관계를 찾아낸다면 위처럼 코드를 유기적으로 작성할 수 있을 것이다. 재귀적인 코드를 구현하는 능력을 기르기 위해선 이런 패턴을 보이는 문제를 풀어보는 경험을 늘릴 수밖에 없겠다.

실행결과

원반 1을 A에서 C로 이동

원반 2를(를) A에서 B로 이동

원반 1을 C에서 B로 이동

원반 3을(를) A에서 C로 이동

원반 1을 B에서 A로 이동

원반 2를(를) B에서 C로 이동