[알고리즘] 하노이의 탑

하노이의 탑 (Towers of Hanoi)

재귀를 활용한 대표적인 알고리즘 문제로 하노이의 탑 문제가 있다. 하노이의 탑은 원하는 위치로 원판을 옮기는 문제다

• 하노이의 탑 : 작은 원반이 위에, 큰 원반이 아래에 위치할 수 있도록 원반을 3개의 기둥 사이에서 옮기는 문제이다.
• 모든 원반은 크기가 다르고 처음에는 모든 원반이 규칙에 맞게 첫번째 기둥에 쌓여있다.
• 이 상태에서 모든 원반을 세 번째 기둥으로 최소의 횟수로 옮기면 된다.
• 원반은 1개씩 옮길 수 있고 큰 원반을 작은 원반 위에 쌓을 수 없다.

 

[원판을 옮길 때 제약사항]

• 맨 위에 있는 원판만 이동 가능
• 한 번에 하나씩만 이동
• 크기가 큰 원판 위에만 작은 원판 이동 가능
• 중간 막대를 이용할 수 있지만 다른 조건이 모두 만족해야 함

#include <stdio.h>

void hanoi_tower(int n, char from, char tmp, char to)
{
    if (n==1) {
        printf("원판1을 %c에서 %c로 옮긴다\n", from, to);	//마지막 원판이므로 기록
    } else {
        hanoi_tower(n-1, from, to, tmp);	           //재귀호출
        printf("원판%d를 %c에서 %c로 옮긴다\n", n, from, to);
        hanoi_tower(n-1, tmp, from, to);	           //재귀호출
    }
}

int main()
{
    hanoi_tower(4, 'a', 'b', 'c'); 	// 4개를 옮기는 경우 출력
}

 

실행 결과

 

원판 4개를 a기둥에서 c기둥으로 이동할 경우 원판의 이동 순서는 >  1 2 1 3 1 2 1 4 1 2 1 3 1 2 1  이다.

가장 큰 원판은 총 횟수 중 항상 중간에 해당한다. 

 

왼쪽노드 > 근노드 > 오른쪽노드 순서로 운행.

 

 

[웹에서 간편하게 코드 실행이 가능한 사이트] wandbox.org/

[참고한 영상] youtu.be/aPYE0anPZqI