[EPPER] 9회 9번

문제

 

 

 

---

풀이

 

재귀함수를 배울 때 꼭 나오는 하노이탑이다. 자매품으로는 피보나치 수열이 있다. 보통은 이동 횟수를 계산하게 하는 경우가 많은데 이건 어떤 원판이 어떻게 이동했는지까지 출력해야 한다. 귀찮아보이지만 어려운 일은 아니다.

 

하노이탑에 대한 설명은 널리고 널렸지만 굳이 내가 또 적어보겠다...n개의 원판을 A에서 C로 옮기고 싶다면 먼저 위에 쌓인 (n-1)개의 원판을 A에서 B로 옮긴다. 그리고 n번째 원판을 A에서 C로 옮기고 남은 (n-1)개의 원판을 B에서 C로 옮기면 된다. 상황에 따라 source, tmp, dest 인자를 서로 옮겨가며 재귀함수를 호출하고 출력하면 된다. 아무리 생각해도 나보다 친절하게 설명한 다른 블로그가 많을 것 같다.

---

소스코드

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int cnt = 0;

void hanoi(int n, char source, char tmp, char dest) {
	if (n == 1) {
		printf("%d: %c->%c\n", n, source, dest);
		cnt++;
	}
	else {
		hanoi(n - 1, source, dest, tmp);
		printf("%d: %c->%c\n", n, source, dest);
		cnt++;
		hanoi(n - 1, tmp, source, dest);
	}
}

int main() {
	int n;

	scanf("%d", &n);
	hanoi(n, 'A', 'B', 'C');
	printf("%d", cnt);
}