[Data Structure] 하노이탑 (Recursion)

하노이 탑 (The Tower of Hanoi)

- 원판은 1번에 1개씩만 옮겨야 한다

- 맨 위에 있는 원판만 이동 가능

- 작은 원판 위에 큰 원판을 올려 놓을 수 없다

n개가 존재하고 막대가 3개 (A, B, C)일 경우

• n-1개의 원판을 B로 옮기고
• 맨 밑에 1개의 원판을 C로 옮기고
• B에 있는 n-1개의 원판을 C로 옮기면 된다

 

※ 코드 구현

#include <stdio.h>

void hanoi(int n, char from, char tmp, char to) {
	/*
	n = 원판의 개수
	from = 시작 지점
	tmp = 경유 지점
	to = 도착 지점
	*/
	/*
	1. n-1개의 원판을 경유 지점에 잠시 놓는다 (여기서의 경유 지점 = to)
	2. 맨밑에 있는 1개의 원판을 최종 도착지점에 옮긴다 (여기서의 경유 지점 = tmp)
	3. 경유 지점에 있는 n-1개의 원판을 최종 도착지점으로 옮긴다 (여기서의 경유 지점 = from)
	*/
	if (n == 1)
		printf("원판 1 : %c -> %c\n", from, to);
	else {
		hanoi(n - 1, from, to, tmp);
		printf("원판 %d : %c -> %c\n", n, from, to);
		hanoi(n - 1, tmp, from, to);
	}
}

int main(void) {
	int n;
	printf("원판 개수 입력 : ");
	scanf("%d", &n);

	hanoi(n, 'A', 'B', 'C');

	return 0;
}